#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#include "rainbow.h"
int r,c;
vpii p;
int grid[2][200000];
vi num[200000];
vpii r1,r2,r12;
void init(int R,int C,int sr,int sc,int M,char *S) {
int i;
r = R,c = C;
sr--,sc--;
p.pb(mp(sr,sc));
for (i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
else if (S[i] == 'S') sr++;
else if (S[i] == 'W') sc--;
else sc++;
p.pb(mp(sr,sc));
}
sort(p.begin(),p.end());
p.resize(unique(p.begin(),p.end())-p.begin());
if (R == 2) {
for (i = 0; i < p.size(); i++) grid[p[i].first][p[i].second] = 1;
int pre = -1;
for (i = 0; i < C; i++) {
if (grid[0][i]) {
if (pre != (i-1)) r1.pb(mp(pre+1,i-1));
pre = i;
}
}
if (pre != C-1) r1.pb(mp(pre+1,C-1));
pre = -1;
for (i = 0; i < C; i++) {
if (grid[1][i]) {
if (pre != (i-1)) r2.pb(mp(pre+1,i-1));
pre = i;
}
}
if (pre != C-1) r2.pb(mp(pre+1,C-1));
pre = -1;
for (i = 0; i < C; i++) {
if (grid[0][i] && grid[1][i]) {
if (pre != (i-1)) r12.pb(mp(pre+1,i-1));
pre = i;
}
}
if (pre != C-1) r12.pb(mp(pre+1,C-1));
}
else {
for (i = 0; i < p.size(); i++) num[p[i].first].pb(p[i].second);
}
}
struct seg { int y,l,r; };
int inter(seg a,seg b) {
return !((a.r < b.l) || (a.l > b.r));
}
seg segs[400000];
vi adjList[400000];
int visited[400000];
int doDFS(int u) {
if (visited[u]) return 0;
int i;
visited[u] = 1;
for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
return 0;
}
int colour(int ar,int ac,int br,int bc) {
ar--,ac--,br--,bc--;
if (r == 2) {
vpii *_use;
if ((ar == 0) && (br == 0)) _use = &r1;
else if ((ar == 0) && (br == 1)) _use = &r12;
else _use = &r2;
vpii &use = *_use;
int l = lower_bound(use.begin(),use.end(),mp(ac,0))-use.begin()-1;
if ((l == -1) || (use[l].second < ac)) l++;
int r = upper_bound(use.begin(),use.end(),mp(bc,c))-use.begin()-1;
return r-l+1;
}
int i,j;
int t = 0;
for (i = ar; i <= br; i++) {
int pre = ac-1;
int pt = t;
for (j = 0; j < num[i].size(); j++) {
if (num[i][j] > bc) break;
if (num[i][j] >= ac) {
if (pre != num[i][j]-1) segs[t++] = (seg){i,pre+1,num[i][j]-1};
pre = num[i][j];
}
}
if (pre != bc) segs[t++] = (seg){i,pre+1,bc};
if (i > ar) {
int t2 = pt-1;
while ((t2 >= 0) && (segs[t2].y == i-1)) t2--;
t2++;
int k = t2;
for (j = pt; j < t; j++) {
while ((k < pt) && (segs[k].r < segs[j].l)) k++;
while ((k < pt) && inter(segs[k],segs[j])) {
adjList[k].pb(j);
adjList[j].pb(k);
k++;
}
k--;
}
}
}
//for (i = 0; i <t;i++)cout<<segs[i].y<<","<<segs[i].l<<","<<segs[i].r<<endl;
int ans = 0;
fill(visited,visited+t,0);
for (i = 0; i < t; i++) {
if (!visited[i]) doDFS(i),ans++;
}
for (i = 0; i < t; i++) adjList[i].clear();
return ans;
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < p.size(); i++) grid[p[i].first][p[i].second] = 1;
~~^~~~~~~~~~
rainbow.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < p.size(); i++) num[p[i].first].pb(p[i].second);
~~^~~~~~~~~~
rainbow.cpp: In function 'int doDFS(int)':
rainbow.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < num[i].size(); j++) {
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
14468 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14528 KB |
Output is correct |
| 3 |
Correct |
111 ms |
18824 KB |
Output is correct |
| 4 |
Correct |
121 ms |
19612 KB |
Output is correct |
| 5 |
Correct |
130 ms |
19752 KB |
Output is correct |
| 6 |
Correct |
153 ms |
19752 KB |
Output is correct |
| 7 |
Correct |
157 ms |
19908 KB |
Output is correct |
| 8 |
Correct |
113 ms |
19908 KB |
Output is correct |
| 9 |
Correct |
114 ms |
19908 KB |
Output is correct |
| 10 |
Correct |
139 ms |
19908 KB |
Output is correct |
| 11 |
Correct |
135 ms |
19908 KB |
Output is correct |
| 12 |
Correct |
130 ms |
19908 KB |
Output is correct |
| 13 |
Correct |
91 ms |
19908 KB |
Output is correct |
| 14 |
Correct |
104 ms |
19972 KB |
Output is correct |
| 15 |
Correct |
112 ms |
19972 KB |
Output is correct |
| 16 |
Correct |
114 ms |
19972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
19972 KB |
Output is correct |
| 2 |
Correct |
49 ms |
25752 KB |
Output is correct |
| 3 |
Correct |
52 ms |
28588 KB |
Output is correct |
| 4 |
Correct |
73 ms |
28588 KB |
Output is correct |
| 5 |
Incorrect |
47 ms |
28588 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
