//#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool a[51][200001];
int dp[4][200001];
bool rr;
void init(int R, int C, int sr, int sc, int M, char *S) {
a[sr][sc]=1;
for (int i=0; i<M; i++){
if (S[i]=='N') sr--;
else if (S[i]=='E') sc++;
else if (S[i]=='S') sr++;
else if (S[i]=='W') sc--;
a[sr][sc]=1;
}
if (R==2){
rr=1;
int cur[4]={};
for (int i=1; i<=C; i++){
if (i==1){
if (!a[1][i]) dp[1][i]=cur[1]=1;
if (!a[2][i]) dp[2][i]=cur[2]=1;
if (!a[1][i]||!a[2][i]) dp[3][i]=cur[3]=1;
} else {
if (a[1][i-1]&&!a[1][i]){
cur[1]++;
dp[1][i]=cur[1];
} else dp[1][i]=dp[1][i-1];
if (a[2][i-1]&&!a[2][i]){
cur[2]++;
dp[2][i]=cur[2];
} else dp[2][i]=dp[2][i-1];
if (a[1][i-1]&&a[2][i-1]&&(!a[1][i]||!a[2][i])){
cur[3]++;
dp[3][i]=cur[3];
} else dp[3][i]=dp[3][i-1];
}
}
}
}
int colour(int ar, int ac, int br, int bc) {
if (rr){
if (ar==br) return dp[ar][bc]-dp[ar][ac]+(!a[ar][ac]);
else return dp[3][bc]-dp[3][ac]+(!a[3][ac]||!a[3][bc]);
} else {
int ans=0;
bool visited[51][51];
for (int i=1; i<51; i++){
for (int j=1; j<51; j++) visited[i][j]=0;
}
for (int i=ar; i<=br; i++){
for (int j=ac; j<=bc; j++){
if (visited[i][j]||a[i][j]) continue;
visited[i][j]=1;
ans++;
queue <pair <int,int> > q;
q.push({i,j});
while (!q.empty()){
pair <int,int> t=q.front();
q.pop();
for (int d=0; d<4; d++){
t.first+=dx[d];
t.second+=dy[d];
if (t.first>=ar&&t.first<=br&&t.second>=ac&&t.second<=bc&&!visited[t.first][t.second]&&!a[t.first][t.second]){
visited[t.first][t.second]=1;
q.push({t.first,t.second});
}
t.first-=dx[d];
t.second-=dy[d];
}
}
}
}
return ans;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
364 KB |
Output is correct |
| 2 |
Correct |
10 ms |
620 KB |
Output is correct |
| 3 |
Correct |
23 ms |
620 KB |
Output is correct |
| 4 |
Correct |
23 ms |
620 KB |
Output is correct |
| 5 |
Correct |
10 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
20 ms |
620 KB |
Output is correct |
| 12 |
Correct |
16 ms |
620 KB |
Output is correct |
| 13 |
Correct |
13 ms |
620 KB |
Output is correct |
| 14 |
Correct |
16 ms |
620 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
364 KB |
Output is correct |
| 2 |
Correct |
10 ms |
620 KB |
Output is correct |
| 3 |
Correct |
23 ms |
620 KB |
Output is correct |
| 4 |
Correct |
23 ms |
620 KB |
Output is correct |
| 5 |
Correct |
10 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
20 ms |
620 KB |
Output is correct |
| 12 |
Correct |
16 ms |
620 KB |
Output is correct |
| 13 |
Correct |
13 ms |
620 KB |
Output is correct |
| 14 |
Correct |
16 ms |
620 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
364 KB |
Output is correct |
| 2 |
Correct |
10 ms |
620 KB |
Output is correct |
| 3 |
Correct |
23 ms |
620 KB |
Output is correct |
| 4 |
Correct |
23 ms |
620 KB |
Output is correct |
| 5 |
Correct |
10 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
20 ms |
620 KB |
Output is correct |
| 12 |
Correct |
16 ms |
620 KB |
Output is correct |
| 13 |
Correct |
13 ms |
620 KB |
Output is correct |
| 14 |
Correct |
16 ms |
620 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
