#include<bits/stdc++.h>
#ifndef LOCAL
#include "rainbow.h"
#endif // LCOAL
using namespace std;
#define pb push_back
#define ld double
#define ll long long
mt19937 rnd(51);
set<pair<int,int>> st;
vector<pair<int,int>> d{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void init(int r, int c, int sr, int sc, int m, char *s) {
st.clear();
sr--, sc--;
st.insert({sr, sc});
for (int i = 0; i < m; i++) {
if (s[i] == 'N') {
sr--;
} else if (s[i] == 'S') {
sr++;
} else if (s[i] == 'W') {
sc--;
} else {
sc++;
}
assert(0 <= sr && sr < r && 0 <= sc && sc < c);
st.insert({sr, sc});
}
}
bool check(int i, int j) {
return (st.find({i, j}) != st.end());
}
int colour(int ar, int ac, int br, int bc) {
ar--, ac--, br--, bc--;
ll n = 0, m = 0, s = 0;
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (check(i, j)) {
n++;
if (i + 1 <= br && check(i + 1, j)) {
m++;
}
if (j + 1 <= bc && check(i, j + 1)) {
m++;
}
if (i + 1 <= br && j + 1 <= bc && check(i + 1, j + 1) && check(i, j + 1) && check(i + 1, j)) {
s++;
}
}
}
}
if (n == (ll)(br - ar + 1) * (bc - ac + 1)) {
return 0;
}
int cnt = 0;
for (int i = ar; i <= br; i++) {
if (check(i, ac)) {
cnt++;
if (i + 1 <= br && check(i + 1, ac)) {
s++;
}
}
if (check(i, bc)) {
cnt++;
if (i + 1 <= br && check(i + 1, bc)) {
s++;
}
}
}
for (int j = ac; j <= bc; j++) {
if (check(ar, j)) {
cnt++;
if (j + 1 <= bc && check(ar, j + 1)) {
s++;
}
}
if (check(br, j)) {
cnt++;
if (j + 1 <= bc && check(br, j + 1)) {
s++;
}
}
}
if (cnt == 0) {
if (n == 0) {
return 1;
} else {
return 2 + m - n;
}
} else {
m += cnt;
vector<pair<int,int>> st;
if (check(ar, ac)) s++;
if (check(ar, bc)) s++;
if (check(br, ac)) s++;
if (check(br, bc)) s++;
return 1 + m - n - s;
}
}
int solve(int ar, int ac, int br, int bc) {
ar--, ac--, br--, bc--;
map<pair<int,int>, int> used;
int cnt = 0;
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (!check(i, j) && !used[{i, j}]) {
cnt++;
used[{i, j}] = 1;
deque<pair<int,int>> q{{i, j}};
while (q.size() > 0) {
int f = q.front().first, s = q.front().second;
q.pop_front();
for (auto to : d) {
f += to.first, s += to.second;
if (ar <= f && f <= br && ac <= s && s <= bc) {
if (!used[{f, s}] && !check(f, s)) {
q.pb({f, s});
used[{f, s}] = 1;
}
}
f -= to.first, s -= to.second;
}
}
}
}
}
return cnt;
}
#ifdef LOCAL
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
int main() {
vector<char> LOL{{'N', 'S', 'W', 'E'}};
int MX = 3;
while (1) {
int r = rnd() % MX + 1, c = rnd() % MX + 1, m = rnd() % MX + 1, q = rnd() % MX + 1;
char s[m];
for (int i = 0; i < m; i++) {
s[i] = LOL[rnd() % 4];
}
int x = rnd() % r, y = rnd() % c;
int sr = x, sc = y;
bool bad = 0;
for (int i = 0; i < m; i++) {
if (s[i] == 'N') {
sr--;
} else if (s[i] == 'S') {
sr++;
} else if (s[i] == 'W') {
sc--;
} else {
sc++;
}
if (!(0 <= sr && sr < r && 0 <= sc && sc < c)) {
bad = 1;
break;
}
}
if (bad) continue;
init(r, c, x + 1, y + 1, m, s);
for (int i = 0; i < q; i++) {
int ar = rnd() % r, br = rnd() % r, ac = rnd() % c, bc = rnd() % c;
if (ar > br) swap(ar, br);
if (ac > bc) swap(ac, bc);
auto res = solve(ar + 1, ac + 1, br + 1, bc + 1), res2 = colour(ar + 1, ac + 1, br + 1, bc + 1);
if (res != res2) {
cout << "BAD" << endl;
cout << r << ' ' << c << ' ' << m << ' ' << endl;
cout << x << ' ' << y << endl;
for (int i = 0; i < m; i++) {
cout << s[i];
}
cout << endl;
cout << ar << ' ' << ac << ' ' << br << ' ' << bc << endl;
cout << res << ' ' << res2 << endl;
return 0;
}
}
cout << "OK" << endl;
}
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}
#endif // LOCAL
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3036 ms |
3156 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 |
Execution timed out |
3042 ms |
5068 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
