#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];
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;
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(get<0>(ran[j-1].back()) + 1);
int cnt = 0, p1 = 0, p2 = 0;
while(p1 < ran[j-1].size() && p2 < ran[j].size()){
//printf("p1=%d p2=%d\n", p1, p2);
if(overlap(ran[j-1][p1], ran[j][p2])){
ch[get<0>(ran[j-1][p1])] = 1;
if(p2 > 0 && overlap(ran[j-1][p1], ran[j][p2-1]))
get<0>(ran[j][p2]) = get<0>(ran[j][p2-1]);
else if(get<0>(ran[j][p2]) == -1)
get<0>(ran[j][p2]) = (p2==0 ? -1 : get<0>(ran[j][p2-1])) + 1;
}
else if(get<0>(ran[j][p2]) == -1)
get<0>(ran[j][p2]) = (p2==0 ? -1 : get<0>(ran[j][p2-1])) + 1;
if(p1+1 == ran[j-1].size())
p2++;
else if(p2+1 == ran[j].size())
p1++;
else if(get<2>(ran[j-1][p1]) < get<2>(ran[j][p2]))
p1++;
else
p2++;
}
for(i=0; i<ch.size(); i++){
if(!ch[i])
ans++;
}
}
ans += get<0>(ran[br].back()) + 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:29:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | auto [s0, s1, e1] = u;
| ^
rainbow.cpp:30:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | auto [e0, s2, e2] = v;
| ^
rainbow.cpp: In function 'int colour2(int, int, int, int)':
rainbow.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(j=0; j+1<board[i].size(); j++){
| ~~~^~~~~~~~~~~~~~~~
rainbow.cpp:46: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]
46 | for(j=0; j<ran[ar].size(); j++)
| ~^~~~~~~~~~~~~~~
rainbow.cpp:53: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]
53 | while(p1 < ran[j-1].size() && p2 < ran[j].size()){
| ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:53: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]
53 | while(p1 < ran[j-1].size() && p2 < ran[j].size()){
| ~~~^~~~~~~~~~~~~~~
rainbow.cpp:64: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]
64 | if(p1+1 == ran[j-1].size())
| ~~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:66:17: 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]
66 | else if(p2+1 == ran[j].size())
| ~~~~~^~~~~~~~~~~~~~~~
rainbow.cpp:73:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(i=0; i<ch.size(); i++){
| ~^~~~~~~~~~
rainbow.cpp:52:7: warning: unused variable 'cnt' [-Wunused-variable]
52 | int cnt = 0, p1 = 0, p2 = 0;
| ^~~
rainbow.cpp:36:12: warning: unused variable 'k' [-Wunused-variable]
36 | int i, j, k;
| ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:82:18: warning: unused variable 'j' [-Wunused-variable]
82 | int ans = 0, i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
10072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19700 KB |
Output is correct |
| 3 |
Correct |
17 ms |
17500 KB |
Output is correct |
| 4 |
Correct |
23 ms |
17500 KB |
Output is correct |
| 5 |
Correct |
17 ms |
17880 KB |
Output is correct |
| 6 |
Correct |
23 ms |
21108 KB |
Output is correct |
| 7 |
Incorrect |
26 ms |
21596 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
10072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
10072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
