#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
char dir[4] = {'N', 'E', 'S', 'W'};
vector<int> board[200009];
vector<tuple<int, int, int> > ran[200009];
int mx[200009];
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R;
m = C;
board[sr].push_back(sc);
for(int i=0; i<M; i++){
int k;
for(k=0; k<4; k++){
if(S[i] == dir[k])
break;
}
sr += dr[k];
sc += dc[k];
board[sr].push_back(sc);
}
for(int i=1; i<=n; i++){
board[i].push_back(0), board[i].push_back(m+1);
sort(board[i].begin(), board[i].end());
board[i].erase(unique(board[i].begin(), board[i].end()), board[i].end());
}
}
bool overlap(tuple<int, int, int> u, tuple<int, int, int> v){
auto [s0, s1, e1] = u;
auto [e0, s2, e2] = v;
return (s2 <= e1 && s1 <= e2);
}
int colour2(int ar, int ac, int br, int bc) {
if(ar>br)
return 0;
int i, j, k;
for(i=ar; i<=br; i++){
//printf("i=%d board.size=%d\n", i,board[i].size());
for(j=0; j+1<board[i].size(); j++){
//printf("i=%d j=%d\n", i, j);
if(board[i][j+1] - board[i][j] >= 2 && max(board[i][j]+1, ac) <= min(board[i][j+1]-1, bc))
ran[i].push_back(make_tuple(-1, max(board[i][j]+1, ac), min(board[i][j+1]-1, bc)));
}
}
int ans = 0;
for(j=0; j<ran[ar].size(); j++)
get<0>(ran[ar][j]) = j;
mx[ar] = (int)ran[ar].size() - 1;
for(j=ar+1; j<=br; j++){
//printf("j=%d\n", j);
//printf("ran[j-1]=%d j=%d\n", ran[j-1].size(), ran[j].size());
vector<bool> ch(mx[j-1] + 1);
vector<int> inv(mx[j-1] + 1);
for(int k=0; k<inv.size(); k++)
inv[k ]= -1;
int cnt = 0, p1 = 0, p2 = 0, last = 0;
while(p1 < ran[j-1].size() && p2 < ran[j].size()){
//printf("p1=%d p2=%d get=%d\n", p1, p2, get<0>(ran[j][p2]));
if(overlap(ran[j-1][p1], ran[j][p2])){
ch[get<0>(ran[j-1][p1])] = 1;
if(p2 > 0 && inv[get<0>(ran[j-1][p1])] != -1)
get<0>(ran[j][p2]) = inv[get<0>(ran[j-1][p1])];
else if(get<0>(ran[j][p2]) == -1){
get<0>(ran[j][p2]) = cnt;
}
}
else if(get<0>(ran[j][p2]) == -1)
get<0>(ran[j][p2]) = cnt;
if(p1+1 == ran[j-1].size()){
for(int p = last; p <= p1; p++){
if(overlap(ran[j-1][p], ran[j][p2]))
inv[get<0>(ran[j-1][p])] = get<0>(ran[j][p2]);
}
if(get<0>(ran[j][p2]) == cnt)
cnt++;
p2++;
last = p1 = 0;
}
else
p1++;
/*
else if(p2+1 == ran[j].size())
p1++;
else if(get<2>(ran[j-1][p1]) < get<2>(ran[j][p2]))
p1++;
else{
for(int p = last; p <= p1; p++){
if(overlap(ran[j-1][p], ran[j][p2]))
inv[get<0>(ran[j-1][p])] = get<0>(ran[j][p2]);
}
if(get<0>(ran[j][p2]) == cnt)
cnt++;
p2++;
last = p1;
}*/
}
//printf("j=%d cnt=%d\n", j, cnt);
mx[j] = cnt-1;
for(i=0; i<ch.size(); i++){
if(!ch[i])
ans++;
}
}
ans += mx[br] + 1;
return ans;
}
int colour(int ar, int ac, int br, int bc) {
int ans = 0, i, j;
int last = ar-1;
for(i=ar; i<=br; i++){
if(upper_bound(board[i].begin(), board[i].end(), bc) - lower_bound(board[i].begin(), board[i].end(), ac) == bc-ac+1){
//printf("i=%d\n", i);
ans += colour2(last+1, ac, i-1, bc);
last = i;
}
}
ans += colour2(last+1, ac, br, bc);
return ans;
}
Compilation message
rainbow.cpp: In function 'bool overlap(std::tuple<int, int, int>, std::tuple<int, int, int>)':
rainbow.cpp:30:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | auto [s0, s1, e1] = u;
| ^
rainbow.cpp:31:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | auto [e0, s2, e2] = v;
| ^
rainbow.cpp: In function 'int colour2(int, int, int, int)':
rainbow.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(j=0; j+1<board[i].size(); j++){
| ~~~^~~~~~~~~~~~~~~~
rainbow.cpp:47:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(j=0; j<ran[ar].size(); j++)
| ~^~~~~~~~~~~~~~~
rainbow.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int k=0; k<inv.size(); k++)
| ~^~~~~~~~~~~
rainbow.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | while(p1 < ran[j-1].size() && p2 < ran[j].size()){
| ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:58:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | while(p1 < ran[j-1].size() && p2 < ran[j].size()){
| ~~~^~~~~~~~~~~~~~~
rainbow.cpp:70:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(p1+1 == ran[j-1].size()){
| ~~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(i=0; i<ch.size(); i++){
| ~^~~~~~~~~~
rainbow.cpp:37:12: warning: unused variable 'k' [-Wunused-variable]
37 | int i, j, k;
| ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:109:18: warning: unused variable 'j' [-Wunused-variable]
109 | int ans = 0, i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
21072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10332 KB |
Output is correct |
| 2 |
Correct |
19 ms |
20272 KB |
Output is correct |
| 3 |
Correct |
18 ms |
18268 KB |
Output is correct |
| 4 |
Correct |
32 ms |
18524 KB |
Output is correct |
| 5 |
Correct |
18 ms |
18388 KB |
Output is correct |
| 6 |
Correct |
25 ms |
21564 KB |
Output is correct |
| 7 |
Incorrect |
48 ms |
22104 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
21072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
21072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
