#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT {
set<pair<int, int>> S;
vector<vector<int>> a;
vector<vector<int>> tmp;
vector<vector<int>> flag;
int R, C;
void init(int _R, int _C) {
R = _R;
C = _C;
a.resize(R + 1);
for (int i = 0; i <= R; i++) {
a[i].resize(C + 1);
}
}
void add(int x, int y) {
if (x < 1 || x > R || y < 1 || y > C || S.find({x, y}) != S.end()) {
return;
}
S.insert({x, y});
a[x][y]++;
}
void build() {
tmp = a;
flag = a;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
a[i][j] += a[i][j - 1];
}
}
for (int j = 1; j <= C; j++) {
for (int i = 1; i <= R; i++) {
a[i][j] += a[i - 1][j];
}
}
}
int get(int x, int y) {
return a[x][y];
}
long long get(int lx, int ly, int rx, int ry) {
return 1LL * (rx - lx + 1) * (ry - ly + 1) - get(rx, ry) + get(rx, ly - 1) + get(lx - 1, ry) - get(lx - 1, ly - 1);
}
int bfs(int lx, int ly, int rx, int ry) {
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
for (int i = lx; i <= rx; i++) {
for (int j = ly; j <= ry; j++) {
flag[i][j] = false;
}
}
int cnt = 0;
for (int i = lx; i <= rx; i++) {
for (int j = ly; j <= ry; j++) {
if (!tmp[i][j] && !flag[i][j]) {
flag[i][j] = true;
cnt++;
deque<pair<int, int>> q = {{i, j}};
while (!q.empty()) {
int cx = q.front().first;
int cy = q.front().second;
q.pop_front();
for (int k = 0; k < 4; k++) {
int nx = cx + dx[k];
int ny = cy + dy[k];
if (lx <= nx && nx <= rx && ly <= ny && ny <= ry && !tmp[nx][ny] && !flag[nx][ny]) {
flag[nx][ny] = true;
q.push_back({nx, ny});
}
}
}
}
}
}
return cnt;
}
} V, row_E, col_E, F;
int max_X, min_X, max_Y, min_Y;
void add(int cx, int cy) {
max_X = max(max_X, cx);
min_X = min(min_X, cx);
max_Y = max(max_Y, cy);
min_Y = min(min_Y, cy);
V.add(cx, cy);
row_E.add(cx - 1, cy);
row_E.add(cx, cy);
col_E.add(cx, cy - 1);
col_E.add(cx, cy);
F.add(cx - 1, cy - 1);
F.add(cx - 1, cy);
F.add(cx, cy - 1);
F.add(cx, cy);
}
void init(int R, int C, int cx, int cy, int M, char *S) {
V.init(R, C);
row_E.init(R, C);
col_E.init(R, C);
F.init(R, C);
max_X = cx;
min_X = cx;
max_Y = cy;
min_Y = cy;
add(cx, cy);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') {
cx--;
}
if (S[i] == 'E') {
cy++;
}
if (S[i] == 'S') {
cx++;
}
if (S[i] == 'W') {
cy--;
}
add(cx, cy);
}
V.build();
row_E.build();
col_E.build();
F.build();
}
int colour(int lx, int ly, int rx, int ry) {
if (lx < min_X && max_X < rx && ly < min_Y && max_Y < ry) {
return 1;
}
return V.bfs(lx, ly, rx, ry);
//return V.get(lx, ly, rx, ry) - row_E.get(lx, ly, rx - 1, ry) - col_E.get(lx, ly, rx, ry - 1) + F.get(lx, ly, rx - 1, ry - 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
7 ms |
676 KB |
Output is correct |
| 3 |
Incorrect |
17 ms |
516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3051 ms |
42964 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
371 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
7 ms |
676 KB |
Output is correct |
| 3 |
Incorrect |
17 ms |
516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
7 ms |
676 KB |
Output is correct |
| 3 |
Incorrect |
17 ms |
516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
