#include <bits/stdc++.h>
#include "rainbow.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
struct BIT2D {
int n;
vector <vector <int>> val;
vector <vector <int>> bit;
BIT2D(int _n = 0) {
n = _n;
bit.resize(n + 5);
val.resize(n + 5);
}
void fakeupdate(int x, int y) {
for (; x <= n; x += x & -x)
val[x].push_back(y);
}
void build() {
for (int i = 1; i <= n; i++) {
sort(ALL(val[i]));
val[i].resize(unique(ALL(val[i])) - val[i].begin());
bit[i].resize(val[i].size() + 1);
}
}
void update(int x, int y) {
for (; x <= n; x += x & -x) {
int i = lower_bound(ALL(val[x]), y) - val[x].begin() + 1;
for (; i < (int) bit[x].size(); i += i & -i)
bit[x][i]++;
}
}
int getsum(int x, int y) {
int res = 0;
for (; x; x -= x & -x) {
int i = upper_bound(ALL(val[x]), y) - val[x].begin();
for (; i; i -= i & -i)
res += bit[x][i];
}
return res;
}
int getsum(int x, int y, int u, int v) {
if (x > u || y > v)
return 0;
return (getsum(u, v) + getsum(x - 1, y - 1))
- (getsum(u, y - 1) + getsum(x - 1, v));
}
};
int fix(char c) {
if (c == 'W')
return 3;
if (c == 'N')
return 2;
if (c == 'E')
return 1;
return 0;
}
BIT2D row, col, cell, face;
set <pair <int, int>> s, r, c, f;
int maxx, maxy, minx, miny;
void add(int sr, int sc) {
s.insert({sr, sc});
s.insert({sr + 1, sc});
s.insert({sr, sc + 1});
s.insert({sr + 1, sc + 1});
f.insert({sr + 1, sc + 1});
r.insert({sr, sc + 1});
r.insert({sr + 1, sc + 1});
c.insert({sr + 1, sc});
c.insert({sr + 1, sc + 1});
maxi(maxx, sr);
maxi(maxy, sc);
mini(minx, sr);
mini(miny, sc);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
row = col = cell = face = BIT2D(R + 1);
minx = maxx = sr;
miny = maxy = sc;
add(sr, sc);
for (int i = 0; i < M; i++) {
int dir = fix(S[i]);
sr += dx[dir];
sc += dy[dir];
add(sr, sc);
}
for (auto [x, y] : s)
cell.fakeupdate(x, y);
for (auto [x, y] : r)
row.fakeupdate(x, y);
for (auto [x, y] : c)
col.fakeupdate(x, y);
for (auto [x, y] : f)
face.fakeupdate(x, y);
cell.build();
row.build();
col.build();
face.build();
for (auto [x, y] : s)
cell.update(x, y);
for (auto [x, y] : r)
row.update(x, y);
for (auto [x, y] : c)
col.update(x, y);
for (auto [x, y] : f)
face.update(x, y);
}
int colour(int x, int y, int u, int v) {
int C = 1 + (x < minx && maxx < u && y < miny && maxy < v);
// cerr << minx << " " << maxx << " " << miny << " " << maxy << "\n";
v++;
u++;
int R = face.getsum(x + 1, y + 1, u, v);
int V = cell.getsum(x + 1, y + 1, u - 1, v - 1);
int E = row.getsum(x + 1, y + 1, u - 1, v)
+ col.getsum(x + 1, y + 1, u, v - 1);
// cerr << V << " " << E << " " << C << " " << R << "\n";
int F = 1 + (C + E - V);
return F - R - 1;
}
//#include "grader.cpp"
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
6 ms |
684 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
6 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
596 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
8 ms |
1000 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
320 ms |
21220 KB |
Output is correct |
4 |
Correct |
469 ms |
34804 KB |
Output is correct |
5 |
Correct |
475 ms |
34448 KB |
Output is correct |
6 |
Correct |
451 ms |
26840 KB |
Output is correct |
7 |
Correct |
481 ms |
26352 KB |
Output is correct |
8 |
Correct |
68 ms |
984 KB |
Output is correct |
9 |
Correct |
469 ms |
34696 KB |
Output is correct |
10 |
Correct |
491 ms |
34432 KB |
Output is correct |
11 |
Correct |
464 ms |
26836 KB |
Output is correct |
12 |
Correct |
356 ms |
32124 KB |
Output is correct |
13 |
Correct |
368 ms |
34648 KB |
Output is correct |
14 |
Correct |
379 ms |
34428 KB |
Output is correct |
15 |
Correct |
379 ms |
26848 KB |
Output is correct |
16 |
Correct |
340 ms |
24892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
958 ms |
137864 KB |
Output is correct |
3 |
Correct |
472 ms |
121536 KB |
Output is correct |
4 |
Correct |
784 ms |
128684 KB |
Output is correct |
5 |
Correct |
510 ms |
111388 KB |
Output is correct |
6 |
Correct |
240 ms |
73928 KB |
Output is correct |
7 |
Correct |
370 ms |
82532 KB |
Output is correct |
8 |
Correct |
337 ms |
32188 KB |
Output is correct |
9 |
Correct |
340 ms |
29844 KB |
Output is correct |
10 |
Correct |
140 ms |
39276 KB |
Output is correct |
11 |
Correct |
269 ms |
50736 KB |
Output is correct |
12 |
Correct |
935 ms |
137852 KB |
Output is correct |
13 |
Correct |
481 ms |
121732 KB |
Output is correct |
14 |
Correct |
784 ms |
128648 KB |
Output is correct |
15 |
Correct |
513 ms |
111392 KB |
Output is correct |
16 |
Correct |
212 ms |
72124 KB |
Output is correct |
17 |
Correct |
409 ms |
86108 KB |
Output is correct |
18 |
Correct |
892 ms |
131636 KB |
Output is correct |
19 |
Correct |
708 ms |
127400 KB |
Output is correct |
20 |
Correct |
819 ms |
134856 KB |
Output is correct |
21 |
Correct |
336 ms |
32120 KB |
Output is correct |
22 |
Correct |
344 ms |
29876 KB |
Output is correct |
23 |
Correct |
138 ms |
39176 KB |
Output is correct |
24 |
Correct |
273 ms |
50816 KB |
Output is correct |
25 |
Correct |
963 ms |
138052 KB |
Output is correct |
26 |
Correct |
478 ms |
121620 KB |
Output is correct |
27 |
Correct |
780 ms |
128556 KB |
Output is correct |
28 |
Correct |
508 ms |
111496 KB |
Output is correct |
29 |
Correct |
217 ms |
72080 KB |
Output is correct |
30 |
Correct |
405 ms |
86304 KB |
Output is correct |
31 |
Correct |
863 ms |
131768 KB |
Output is correct |
32 |
Correct |
729 ms |
127624 KB |
Output is correct |
33 |
Correct |
791 ms |
134948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
6 ms |
684 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
6 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
596 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
8 ms |
1000 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
797 ms |
27088 KB |
Output is correct |
19 |
Correct |
265 ms |
4844 KB |
Output is correct |
20 |
Correct |
178 ms |
3832 KB |
Output is correct |
21 |
Correct |
206 ms |
4144 KB |
Output is correct |
22 |
Correct |
233 ms |
4544 KB |
Output is correct |
23 |
Correct |
250 ms |
4684 KB |
Output is correct |
24 |
Correct |
223 ms |
4040 KB |
Output is correct |
25 |
Correct |
234 ms |
4296 KB |
Output is correct |
26 |
Correct |
243 ms |
4644 KB |
Output is correct |
27 |
Correct |
454 ms |
21608 KB |
Output is correct |
28 |
Correct |
352 ms |
13120 KB |
Output is correct |
29 |
Correct |
435 ms |
19996 KB |
Output is correct |
30 |
Correct |
788 ms |
50596 KB |
Output is correct |
31 |
Correct |
3 ms |
340 KB |
Output is correct |
32 |
Correct |
602 ms |
23368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
6 ms |
684 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
6 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
596 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
8 ms |
1000 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
797 ms |
27088 KB |
Output is correct |
19 |
Correct |
265 ms |
4844 KB |
Output is correct |
20 |
Correct |
178 ms |
3832 KB |
Output is correct |
21 |
Correct |
206 ms |
4144 KB |
Output is correct |
22 |
Correct |
233 ms |
4544 KB |
Output is correct |
23 |
Correct |
250 ms |
4684 KB |
Output is correct |
24 |
Correct |
223 ms |
4040 KB |
Output is correct |
25 |
Correct |
234 ms |
4296 KB |
Output is correct |
26 |
Correct |
243 ms |
4644 KB |
Output is correct |
27 |
Correct |
454 ms |
21608 KB |
Output is correct |
28 |
Correct |
352 ms |
13120 KB |
Output is correct |
29 |
Correct |
435 ms |
19996 KB |
Output is correct |
30 |
Correct |
788 ms |
50596 KB |
Output is correct |
31 |
Correct |
3 ms |
340 KB |
Output is correct |
32 |
Correct |
602 ms |
23368 KB |
Output is correct |
33 |
Correct |
958 ms |
137864 KB |
Output is correct |
34 |
Correct |
472 ms |
121536 KB |
Output is correct |
35 |
Correct |
784 ms |
128684 KB |
Output is correct |
36 |
Correct |
510 ms |
111388 KB |
Output is correct |
37 |
Correct |
240 ms |
73928 KB |
Output is correct |
38 |
Correct |
370 ms |
82532 KB |
Output is correct |
39 |
Correct |
337 ms |
32188 KB |
Output is correct |
40 |
Correct |
340 ms |
29844 KB |
Output is correct |
41 |
Correct |
140 ms |
39276 KB |
Output is correct |
42 |
Correct |
269 ms |
50736 KB |
Output is correct |
43 |
Correct |
935 ms |
137852 KB |
Output is correct |
44 |
Correct |
481 ms |
121732 KB |
Output is correct |
45 |
Correct |
784 ms |
128648 KB |
Output is correct |
46 |
Correct |
513 ms |
111392 KB |
Output is correct |
47 |
Correct |
212 ms |
72124 KB |
Output is correct |
48 |
Correct |
409 ms |
86108 KB |
Output is correct |
49 |
Correct |
892 ms |
131636 KB |
Output is correct |
50 |
Correct |
708 ms |
127400 KB |
Output is correct |
51 |
Correct |
819 ms |
134856 KB |
Output is correct |
52 |
Correct |
336 ms |
32120 KB |
Output is correct |
53 |
Correct |
344 ms |
29876 KB |
Output is correct |
54 |
Correct |
138 ms |
39176 KB |
Output is correct |
55 |
Correct |
273 ms |
50816 KB |
Output is correct |
56 |
Correct |
963 ms |
138052 KB |
Output is correct |
57 |
Correct |
478 ms |
121620 KB |
Output is correct |
58 |
Correct |
780 ms |
128556 KB |
Output is correct |
59 |
Correct |
508 ms |
111496 KB |
Output is correct |
60 |
Correct |
217 ms |
72080 KB |
Output is correct |
61 |
Correct |
405 ms |
86304 KB |
Output is correct |
62 |
Correct |
863 ms |
131768 KB |
Output is correct |
63 |
Correct |
729 ms |
127624 KB |
Output is correct |
64 |
Correct |
791 ms |
134948 KB |
Output is correct |
65 |
Correct |
320 ms |
21220 KB |
Output is correct |
66 |
Correct |
469 ms |
34804 KB |
Output is correct |
67 |
Correct |
475 ms |
34448 KB |
Output is correct |
68 |
Correct |
451 ms |
26840 KB |
Output is correct |
69 |
Correct |
481 ms |
26352 KB |
Output is correct |
70 |
Correct |
68 ms |
984 KB |
Output is correct |
71 |
Correct |
469 ms |
34696 KB |
Output is correct |
72 |
Correct |
491 ms |
34432 KB |
Output is correct |
73 |
Correct |
464 ms |
26836 KB |
Output is correct |
74 |
Correct |
356 ms |
32124 KB |
Output is correct |
75 |
Correct |
368 ms |
34648 KB |
Output is correct |
76 |
Correct |
379 ms |
34428 KB |
Output is correct |
77 |
Correct |
379 ms |
26848 KB |
Output is correct |
78 |
Correct |
340 ms |
24892 KB |
Output is correct |
79 |
Correct |
726 ms |
35632 KB |
Output is correct |
80 |
Correct |
782 ms |
33292 KB |
Output is correct |
81 |
Correct |
425 ms |
42668 KB |
Output is correct |
82 |
Correct |
546 ms |
54216 KB |
Output is correct |
83 |
Correct |
1262 ms |
141520 KB |
Output is correct |
84 |
Correct |
752 ms |
125168 KB |
Output is correct |
85 |
Correct |
1182 ms |
132016 KB |
Output is correct |
86 |
Correct |
874 ms |
114956 KB |
Output is correct |
87 |
Correct |
433 ms |
75504 KB |
Output is correct |
88 |
Correct |
631 ms |
89640 KB |
Output is correct |
89 |
Correct |
1116 ms |
135224 KB |
Output is correct |
90 |
Correct |
1279 ms |
130904 KB |
Output is correct |
91 |
Correct |
1125 ms |
138516 KB |
Output is correct |