Tasks Details
hard
1.
CakeFactory
Count the number of cakes consisting of K different layers in the order 1, 2, ..., K that will be created after a sequence of operations of putting a layer on some interval.
Task Score
100%
Correctness
100%
Performance
100%
There is a cake factory producing K-flavored cakes. Flavors are numbered from 1 to K. A cake should consist of exactly K layers, each of a different flavor. It is very important that every flavor appears in exactly one cake layer and that the flavor layers are ordered from 1 to K from bottom to top. Otherwise the cake doesn't taste good enough to be sold. For example, for K = 3, cake [1, 2, 3] is well-prepared and can be sold, whereas cakes [1, 3, 2] and [1, 2, 3, 3] are not well-prepared.
The factory has N cake forms arranged in a row, numbered from 1 to N. Initially, all forms are empty. At the beginning of the day a machine for producing cakes executes a sequence of M instructions (numbered from 0 to M−1) one by one. The J-th instruction adds a layer of flavor C[J] to all forms from A[J] to B[J], inclusive.
What is the number of well-prepared cakes after executing the sequence of M instructions?
Write a function:
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C);
that, given two integers N and K and three arrays of integers A, B, C describing the sequence, returns the number of well-prepared cakes after executing the sequence of instructions.
Examples:
1. Given N = 5, K = 3, A = [1, 1, 4, 1, 4], B = [5, 2, 5, 5, 4] and C = [1, 2, 2, 3, 3].
There is a sequence of five instructions:
- The 0th instruction puts a layer of flavor 1 in all forms from 1 to 5.
- The 1st instruction puts a layer of flavor 2 in all forms from 1 to 2.
- The 2nd instruction puts a layer of flavor 2 in all forms from 4 to 5.
- The 3rd instruction puts a layer of flavor 3 in all forms from 1 to 5.
- The 4th instruction puts a layer of flavor 3 in the 4th form.
The function should return 3. The cake in form 3 is missing flavor 2, and the cake in form 5 has additional flavor 3. The well-prepared cakes are forms 1, 2 and 5.
2. Given N = 6, K = 4, A = [1, 2, 1, 1], B = [3, 3, 6, 6] and C = [1, 2, 3, 4],
the function should return 2. The 2nd and 3rd cakes are well-prepared.
3. Given N = 3, K = 2, A = [1, 3, 3, 1, 1], B = [2, 3, 3, 1, 2] and C = [1, 2, 1, 2, 2],
the function should return 1. Only the 2nd cake is well-prepared.
4. Given N = 5, K = 2, A = [1, 1, 2], B = [5, 5, 3] and C = [1, 2, 1],
the function should return 3. The 1st, 4th and 5th cakes are well-prepared.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- M is an integer within the range [1..200,000];
- each element of arrays A and B is an integer within the range [1..N];
- each element of array C is an integer within the range [1..K];
- for every integer J, A[J] ≤ B[J];
- arrays A, B and C have the same length, equal to M.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 7 minutes
Notes
not defined yet
Code: 21:51:37 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int K, int[] A, int[] B, int[] C) {
// write your code in Java SE 8
}
}
Code: 21:51:48 UTC,
cpp,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
for ( auto it = removed.begin(); it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Code: 21:52:01 UTC,
cpp,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
for ( auto it = removed.begin(); it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Code: 21:52:31 UTC,
cpp,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
auto startit = removed.upper_bound( key );
if (startit != removed.begin() ) startit
for ( auto it = removed.begin(); it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Code: 21:52:42 UTC,
cpp,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
auto startit = removed.upper_bound( key );
if (startit != removed.begin() ) startit--;
for ( auto it = startit; it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Code: 21:52:48 UTC,
cpp,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
auto startit = removed.upper_bound( key );
if (startit != removed.begin() ) startit--;
for ( auto it = startit; it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Analysis
Code: 21:57:26 UTC,
cpp,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
auto startit = removed.uppe_bound( key );
if (startit != removed.begin() ) startit--;
for ( auto it = startit; it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Code: 21:57:30 UTC,
cpp,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
auto startit = removed.lower_bound( key );
if (startit != removed.begin() ) startit--;
for ( auto it = startit; it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Analysis
Code: 21:58:08 UTC,
cpp,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
auto startit = removed.lower_bound( key );
if (startit != removed.begin() ) startit--;
for ( auto it = startit; it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}
Analysis
Code: 21:58:12 UTC,
cpp,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
#include<algorithm>
using namespace std;
bool dbg = false;
int solution(int N, int K, vector<int> &A, vector<int> &B, vector<int> &C) {
// write your code in C++14 (g++ 6.2.0)
map<int, int> next;
map<int, int> removed;
vector<int> col(N+3, 0);
vector<bool> ok(N+3, true);
next[1]=N;
next[N+1]=N+2;
for( auto i = 0; i < C.size(); ++i ){
int a = A[i];
int b = B[i];
int c = C[i];
if (dbg) cout << "new painting: " << a << ":" << b << " col:" << c << endl;
// slice begin
auto ms = next.upper_bound( a );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key < a && a <= val ){
if (dbg) cout << "1) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << a-1 << "] + [" << a << ":" << val << "]" << endl;
next[key] = a - 1;
next[a] = val;
col[a] = col[key];
}
}
// slice end
ms = next.upper_bound( b );
if ( ms != next.end() ){ // is something to paint
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if ( key <= b && b < val ){
if (dbg) cout << "2) slice [" << key << ":" << val << "] ->" << "[" << key << ":" << b << "] + [" << b+1 << ":" << val << "]" << endl;
next[key] = b;
next[b+1] = val;
col[b+1] = col[key];
}
}
if (dbg) {
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
}
// painting
ms = next.upper_bound(a);
if ( ms != next.end() ){
if ( ms != next.begin() ) --ms;
auto key = (*ms).first;
auto val = (*ms).second;
if (dbg) cout << "start painting---" << endl;
while ( key <= b ){
int color = col[key];
if ( a <= key && val <= b ){
if (dbg) cout << "painting [" << key << ":" << val << "] =" << color << endl;
if( c != color + 1){
if (dbg) cout << "different colors, remove" << endl;
/*for (int i = key; i <= val; ++i){
ok[i]=false;
}*/
int _key = key;
int _val = val;
auto startit = removed.lower_bound( key );
if (startit != removed.begin() ) startit--;
for ( auto it = startit; it != removed.end();){
auto rmkey = (*it).first;
auto rmval = (*it).second;
if ( rmval < key ){
++it;
} else if ( val < rmkey ){
break;
} else {
it = removed.erase(it);
_key = min( _key, rmkey );
_val = max( _val, rmval );
}
}
removed[_key] = _val;
ms = next.erase(ms);
} else {
//++ms;
ms = next.erase(ms);
col[key]=0; //++;
if (dbg) cout << "painting succeeded - reoved" << endl;
}
} else {
if (dbg) cout << "skip " << key << ":" << val << endl;
++ms;
}
next[a] = b;
col[a] = c;
if (dbg) cout << "new [" << a << ":" << b << "]=" << color << endl;
key = (*ms).first;
val = (*ms).second;
}
}
}
if (dbg){
cout << "final results:" << endl;
for(auto x : next){
cout << "map " << x.first << ":" << x.second << " =" << col[x.first] << endl;
}
for(auto x : removed){
cout << "removed " << x.first << ":" << x.second << " =" << endl;
}
}
int ret = 0;
for (auto x : removed ){
auto key = x.first;
auto val = x.second;
for (int i = key; i <= val; i++) ok[i] = false;
}
for (auto x : next){
auto key = x.first;
auto val = x.second;
auto color = col[key];
if ( color == K ){
for ( int i = key; i <= val; ++i){
if (ok[i]) ret++;
//ret = ret + val - key + 1;
}
}
}
return ret;
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M*log(N)) or O(N+M) or O((M+N)*log(N)) or O(N+M*log(M))
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
expand all
Performance tests
1.
0.048 s
OK
2.
0.024 s
OK
1.
0.004 s
OK
2.
0.040 s
OK
3.
0.036 s
OK
4.
0.012 s
OK
5.
0.036 s
OK
1.
0.028 s
OK
2.
0.136 s
OK
3.
0.108 s
OK
4.
0.128 s
OK
5.
0.124 s
OK
6.
0.140 s
OK