#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ii pair<int,int>
#define dbg(x) cerr << #x << ": " << x << endl;
#define raya cerr << "=================" << endl;
const int N = 2e5+5;
vector<vector<int>> grid;
int rows, cols;
map<char,ii> to = {{'N', {-1, 0}}, {'S', {1, 0}}, {'W', {0, -1}}, {'E', {0, 1}}};
int arriba[N], abajo[N], ambos[N];
set<int> nodes;
set<ii> edges;
void insertNodes(int row, int col){
int pri = col * (rows + 1) + row + 1;
nodes.insert(pri);
nodes.insert(pri+1);
nodes.insert(pri + rows+1);
nodes.insert(pri+1 + rows+1);
edges.insert({pri, pri+1});
edges.insert({pri, pri + rows+1});
edges.insert({pri+1, pri+1 + rows+1});
edges.insert({pri+rows+1, pri+1+rows+1});
}
void init(int R, int C, int sr, int sc, int M, char *s){
rows = R;
cols = C;
// sr--, sc--;
if(rows == 2){
grid.assign(4, vector<int>(cols+2, 0));
} else if(rows <= 50 && cols <= 50) {
grid.assign(rows+2, vector<int>(cols+2, 0));
}
if(rows <= 50 && cols <= 50){
ii pos = {sr, sc};
grid[pos.first][pos.second] = 1;
for(int i=0; i<M; ++i){
char c = s[i];
pos.first += to[c].first;
pos.second += to[c].second;
grid[pos.first][pos.second] = 1;
}
}
if(rows == 2){
// subtask 2
arriba[1] = (grid[1][1] == 0);
abajo[1] = (grid[2][1] == 0);
for(int i=2; i<=cols; ++i){
arriba[i] = (grid[1][i-1] == 1 && grid[1][i] == 0);
abajo[i] = (grid[2][i-1] == 1 && grid[2][i] == 0);
}
for(int i=2; i<=cols; ++i){
arriba[i] += arriba[i-1];
abajo[i] += abajo[i-1];
}
// ambos
ambos[1] = (grid[1][1] == 0 && grid[1][1] == 0);
for(int i=2; i<=cols; ++i){
if(grid[1][i-1] == 1 or grid[2][i-1] == 1){
ambos[i] = (grid[1][i] == 0 && grid[2][i] == 0);
}
}
for(int i=2; i<=cols; ++i){
ambos[i] += ambos[i-1];
}
}
// subtask 3
ii pos = {sr, sc};
insertNodes(pos.first, pos.second);
for(int i=0; i<M; ++i){
char c = s[i];
pos.first += to[c].first;
pos.second += to[c].second;
insertNodes(pos.first, pos.second);
}
}
void clear(){
for(int i=1; i<=rows; ++i){
for(int j=1; j<=cols; ++j){
if(grid[i][j] == 2) grid[i][j] = 0;
}
}
}
vector<ii> mov = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int i, int j, int ar, int ac, int br, int bc){
for(auto tmp : mov){
int ni = i + tmp.first;
int nj = j + tmp.second;
if(ni >= ar && ni <= br && nj >= ac && nj <= bc && grid[ni][nj] == 0){
grid[ni][nj] = 2;
dfs(ni, nj, ar, ac, br, bc);
}
}
}
int colour(int ar, int ac, int br, int bc){
// ar--, ac--;
// br--, bc--;
if(rows == 2){
// subtask 2
if(ar+1 == br){
// ambos
int res = arriba[bc] + abajo[bc];
int quitar = ambos[bc];
if(ac > 0){
res -= arriba[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0);
res -= abajo[ac-1] - (grid[2][ac-1] == 0 && grid[2][ac] == 0);
quitar -= ambos[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0 && grid[2][ac-1] == 0 && grid[2][ac] == 0);
}
res -= quitar;
return res;
}
// arriba
if(ar == 0){
int res = arriba[bc];
if(ac > 0){
res -= arriba[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0);
}
return res;
}
// abajo
assert(ar == 1);
int res = abajo[bc];
if(ac > 0){
res -= abajo[ac-1] - (grid[2][ac-1] == 0 && grid[2][ac] == 0);
}
return res;
}
if(rows <= 50 && cols <= 50){
// subtask 1
int ans = 0;
for(int i=ar; i<=br; ++i){
for(int j=ac; j<=bc; ++j){
if(grid[i][j] == 0){
ans++;
grid[i][j] = 2;
dfs(i, j, ar, ac, br, bc);
}
}
}
clear();
return ans;
}
// only one query (subtask 3)
}
// int main(){
// init(4, 4, 2, 1, 3, "EES");
// }
Compilation message
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:169:1: warning: control reaches end of non-void function [-Wreturn-type]
169 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
7 ms |
600 KB |
Output is correct |
3 |
Correct |
12 ms |
604 KB |
Output is correct |
4 |
Correct |
12 ms |
604 KB |
Output is correct |
5 |
Correct |
9 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
12 ms |
604 KB |
Output is correct |
12 |
Correct |
10 ms |
604 KB |
Output is correct |
13 |
Correct |
9 ms |
604 KB |
Output is correct |
14 |
Correct |
7 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 6 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Runtime error |
105 ms |
48316 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
7 ms |
600 KB |
Output is correct |
3 |
Correct |
12 ms |
604 KB |
Output is correct |
4 |
Correct |
12 ms |
604 KB |
Output is correct |
5 |
Correct |
9 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
12 ms |
604 KB |
Output is correct |
12 |
Correct |
10 ms |
604 KB |
Output is correct |
13 |
Correct |
9 ms |
604 KB |
Output is correct |
14 |
Correct |
7 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 6 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
7 ms |
600 KB |
Output is correct |
3 |
Correct |
12 ms |
604 KB |
Output is correct |
4 |
Correct |
12 ms |
604 KB |
Output is correct |
5 |
Correct |
9 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
12 ms |
604 KB |
Output is correct |
12 |
Correct |
10 ms |
604 KB |
Output is correct |
13 |
Correct |
9 ms |
604 KB |
Output is correct |
14 |
Correct |
7 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 6 |
17 |
Halted |
0 ms |
0 KB |
- |