#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "rainbow.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
set <pair <int, int>> V, X, Y, s;
int maxx, minx, maxy, miny;
struct range_tree {
vector <int> BIT[N], dta[N];
vector <tuple <int, int, int>> work;
void add(int x, int y, int val) {
work.push_back({x, y, val});
for (; x < N; x += x & - x)
dta[x].push_back(y);
}
void build() {
for (int i = 0; i < N; ++i) {
sort(dta[i].begin(), dta[i].end());
dta[i].erase(unique(dta[i].begin(), dta[i].end()), dta[i].end());
BIT[i].assign(dta[i].size() + 10, 0);
}
for (auto [x, y, val]: work) {
for (; x < N; x += x & - x) {
int z = lower_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin() + 1;
for (; z < BIT[x].size(); z += z & - z)
BIT[x][z] += val;
}
}
}
int get(int x, int y) {
int ans = 0;
for (; x; x -= x & - x) {
int z = upper_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin();
for (; z; z -= z & - z)
ans += BIT[x][z];
}
return ans;
}
int get(int x, int y, int u, int v) {
return get(u, v) - get(x - 1, v) - get(u, y - 1) + get(x - 1, y - 1);
}
} cnt[4];
void init(int R, int C, int x, int y, int M, char *S) {
s.insert({x, y});
maxx = minx = x;
++maxx;
maxy = miny = y;
++maxy;
for (int i = 0; i < M; ++i) {
if (S[i] == 'N') --x;
if (S[i] == 'S') ++x;
if (S[i] == 'E') ++y;
if (S[i] == 'W') --y;
maxx = max(maxx, x + 1);
minx = min(minx, x);
maxy = max(maxy, y + 1);
miny = min(miny, y);
s.insert({x, y});
}
for (auto [x, y]: s) {
V.insert({x, y});
V.insert({x, y + 1});
V.insert({x + 1, y});
V.insert({x + 1, y + 1});
X.insert({x, y});
Y.insert({x, y});
X.insert({x, y + 1});
Y.insert({x + 1, y});
}
for (auto [x, y]: s) cnt[0].add(x, y, 1);
for (auto [x, y]: V) cnt[1].add(x, y, 1);
for (auto [x, y]: X) cnt[2].add(x, y, 1);
for (auto [x, y]: Y) cnt[3].add(x, y, 1);
cnt[0].build();
cnt[1].build();
cnt[2].build();
cnt[3].build();
}
int colour(int _x, int _y, int _u, int _v) {
++_u, ++_v;
int v = cnt[1].get(_x + 1, _y + 1, _u - 1, _v - 1);
int e = cnt[2].get(_x, _y + 1, _u - 1, _v - 1) + cnt[3].get(_x + 1, _y, _u - 1, _v - 1);
int r = cnt[0].get(_x, _y, _u - 1, _v - 1);
return e - v + 1 + (_x < minx && _u > maxx && _y < miny && _v > maxy) - r;
}
////
//static int R, C, M, Q;
//static int sr, sc;
//static char S[100000 + 5];
//
//int main() {
// 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;
//}
Compilation message
rainbow.cpp: In member function 'void range_tree::build()':
rainbow.cpp:34:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for (auto [x, y, val]: work) {
| ^
rainbow.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (; z < BIT[x].size(); z += z & - z)
| ~~^~~~~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | for (auto [x, y]: s) {
| ^
rainbow.cpp:85:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for (auto [x, y]: s) cnt[0].add(x, y, 1);
| ^
rainbow.cpp:86:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
86 | for (auto [x, y]: V) cnt[1].add(x, y, 1);
| ^
rainbow.cpp:87:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | for (auto [x, y]: X) cnt[2].add(x, y, 1);
| ^
rainbow.cpp:88:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | for (auto [x, y]: Y) cnt[3].add(x, y, 1);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
75656 KB |
Output is correct |
2 |
Correct |
77 ms |
76204 KB |
Output is correct |
3 |
Correct |
65 ms |
75556 KB |
Output is correct |
4 |
Correct |
68 ms |
75640 KB |
Output is correct |
5 |
Correct |
77 ms |
76400 KB |
Output is correct |
6 |
Correct |
59 ms |
75356 KB |
Output is correct |
7 |
Correct |
58 ms |
75372 KB |
Output is correct |
8 |
Correct |
58 ms |
75340 KB |
Output is correct |
9 |
Correct |
68 ms |
75360 KB |
Output is correct |
10 |
Correct |
62 ms |
75340 KB |
Output is correct |
11 |
Correct |
63 ms |
75792 KB |
Output is correct |
12 |
Correct |
72 ms |
75992 KB |
Output is correct |
13 |
Correct |
84 ms |
76624 KB |
Output is correct |
14 |
Correct |
86 ms |
76880 KB |
Output is correct |
15 |
Correct |
63 ms |
75340 KB |
Output is correct |
16 |
Correct |
60 ms |
75388 KB |
Output is correct |
17 |
Correct |
60 ms |
75336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
75388 KB |
Output is correct |
2 |
Correct |
60 ms |
75336 KB |
Output is correct |
3 |
Correct |
954 ms |
142460 KB |
Output is correct |
4 |
Correct |
1603 ms |
189304 KB |
Output is correct |
5 |
Correct |
1539 ms |
186932 KB |
Output is correct |
6 |
Correct |
1240 ms |
162064 KB |
Output is correct |
7 |
Correct |
1240 ms |
156952 KB |
Output is correct |
8 |
Correct |
120 ms |
79016 KB |
Output is correct |
9 |
Correct |
1510 ms |
189216 KB |
Output is correct |
10 |
Correct |
1542 ms |
186500 KB |
Output is correct |
11 |
Correct |
1255 ms |
161940 KB |
Output is correct |
12 |
Correct |
1558 ms |
182504 KB |
Output is correct |
13 |
Correct |
1405 ms |
189172 KB |
Output is correct |
14 |
Correct |
1405 ms |
186504 KB |
Output is correct |
15 |
Correct |
1178 ms |
161928 KB |
Output is correct |
16 |
Correct |
1146 ms |
163264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
75340 KB |
Output is correct |
2 |
Correct |
790 ms |
152748 KB |
Output is correct |
3 |
Correct |
460 ms |
148112 KB |
Output is correct |
4 |
Correct |
745 ms |
153460 KB |
Output is correct |
5 |
Correct |
444 ms |
131984 KB |
Output is correct |
6 |
Correct |
183 ms |
88168 KB |
Output is correct |
7 |
Correct |
293 ms |
98220 KB |
Output is correct |
8 |
Correct |
1002 ms |
163172 KB |
Output is correct |
9 |
Correct |
903 ms |
154344 KB |
Output is correct |
10 |
Correct |
187 ms |
89404 KB |
Output is correct |
11 |
Correct |
434 ms |
110956 KB |
Output is correct |
12 |
Correct |
806 ms |
152752 KB |
Output is correct |
13 |
Correct |
435 ms |
148080 KB |
Output is correct |
14 |
Correct |
717 ms |
153464 KB |
Output is correct |
15 |
Correct |
447 ms |
132044 KB |
Output is correct |
16 |
Correct |
176 ms |
85788 KB |
Output is correct |
17 |
Correct |
314 ms |
101584 KB |
Output is correct |
18 |
Correct |
756 ms |
154400 KB |
Output is correct |
19 |
Correct |
658 ms |
151840 KB |
Output is correct |
20 |
Correct |
755 ms |
157944 KB |
Output is correct |
21 |
Correct |
989 ms |
163144 KB |
Output is correct |
22 |
Correct |
895 ms |
154348 KB |
Output is correct |
23 |
Correct |
210 ms |
89512 KB |
Output is correct |
24 |
Correct |
387 ms |
110968 KB |
Output is correct |
25 |
Correct |
819 ms |
152724 KB |
Output is correct |
26 |
Correct |
458 ms |
148140 KB |
Output is correct |
27 |
Correct |
719 ms |
153464 KB |
Output is correct |
28 |
Correct |
443 ms |
131912 KB |
Output is correct |
29 |
Correct |
178 ms |
85804 KB |
Output is correct |
30 |
Correct |
316 ms |
101568 KB |
Output is correct |
31 |
Correct |
762 ms |
154488 KB |
Output is correct |
32 |
Correct |
668 ms |
151856 KB |
Output is correct |
33 |
Correct |
732 ms |
157968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
75656 KB |
Output is correct |
2 |
Correct |
77 ms |
76204 KB |
Output is correct |
3 |
Correct |
65 ms |
75556 KB |
Output is correct |
4 |
Correct |
68 ms |
75640 KB |
Output is correct |
5 |
Correct |
77 ms |
76400 KB |
Output is correct |
6 |
Correct |
59 ms |
75356 KB |
Output is correct |
7 |
Correct |
58 ms |
75372 KB |
Output is correct |
8 |
Correct |
58 ms |
75340 KB |
Output is correct |
9 |
Correct |
68 ms |
75360 KB |
Output is correct |
10 |
Correct |
62 ms |
75340 KB |
Output is correct |
11 |
Correct |
63 ms |
75792 KB |
Output is correct |
12 |
Correct |
72 ms |
75992 KB |
Output is correct |
13 |
Correct |
84 ms |
76624 KB |
Output is correct |
14 |
Correct |
86 ms |
76880 KB |
Output is correct |
15 |
Correct |
63 ms |
75340 KB |
Output is correct |
16 |
Correct |
60 ms |
75388 KB |
Output is correct |
17 |
Correct |
60 ms |
75336 KB |
Output is correct |
18 |
Correct |
952 ms |
117056 KB |
Output is correct |
19 |
Correct |
344 ms |
81276 KB |
Output is correct |
20 |
Correct |
239 ms |
79188 KB |
Output is correct |
21 |
Correct |
273 ms |
79796 KB |
Output is correct |
22 |
Correct |
291 ms |
80056 KB |
Output is correct |
23 |
Correct |
334 ms |
81156 KB |
Output is correct |
24 |
Correct |
304 ms |
79600 KB |
Output is correct |
25 |
Correct |
316 ms |
80068 KB |
Output is correct |
26 |
Correct |
327 ms |
80220 KB |
Output is correct |
27 |
Correct |
552 ms |
109208 KB |
Output is correct |
28 |
Correct |
416 ms |
93592 KB |
Output is correct |
29 |
Correct |
518 ms |
105712 KB |
Output is correct |
30 |
Correct |
1046 ms |
157980 KB |
Output is correct |
31 |
Correct |
67 ms |
75532 KB |
Output is correct |
32 |
Correct |
679 ms |
112544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
75656 KB |
Output is correct |
2 |
Correct |
77 ms |
76204 KB |
Output is correct |
3 |
Correct |
65 ms |
75556 KB |
Output is correct |
4 |
Correct |
68 ms |
75640 KB |
Output is correct |
5 |
Correct |
77 ms |
76400 KB |
Output is correct |
6 |
Correct |
59 ms |
75356 KB |
Output is correct |
7 |
Correct |
58 ms |
75372 KB |
Output is correct |
8 |
Correct |
58 ms |
75340 KB |
Output is correct |
9 |
Correct |
68 ms |
75360 KB |
Output is correct |
10 |
Correct |
62 ms |
75340 KB |
Output is correct |
11 |
Correct |
63 ms |
75792 KB |
Output is correct |
12 |
Correct |
72 ms |
75992 KB |
Output is correct |
13 |
Correct |
84 ms |
76624 KB |
Output is correct |
14 |
Correct |
86 ms |
76880 KB |
Output is correct |
15 |
Correct |
63 ms |
75340 KB |
Output is correct |
16 |
Correct |
60 ms |
75388 KB |
Output is correct |
17 |
Correct |
60 ms |
75336 KB |
Output is correct |
18 |
Correct |
952 ms |
117056 KB |
Output is correct |
19 |
Correct |
344 ms |
81276 KB |
Output is correct |
20 |
Correct |
239 ms |
79188 KB |
Output is correct |
21 |
Correct |
273 ms |
79796 KB |
Output is correct |
22 |
Correct |
291 ms |
80056 KB |
Output is correct |
23 |
Correct |
334 ms |
81156 KB |
Output is correct |
24 |
Correct |
304 ms |
79600 KB |
Output is correct |
25 |
Correct |
316 ms |
80068 KB |
Output is correct |
26 |
Correct |
327 ms |
80220 KB |
Output is correct |
27 |
Correct |
552 ms |
109208 KB |
Output is correct |
28 |
Correct |
416 ms |
93592 KB |
Output is correct |
29 |
Correct |
518 ms |
105712 KB |
Output is correct |
30 |
Correct |
1046 ms |
157980 KB |
Output is correct |
31 |
Correct |
67 ms |
75532 KB |
Output is correct |
32 |
Correct |
679 ms |
112544 KB |
Output is correct |
33 |
Correct |
790 ms |
152748 KB |
Output is correct |
34 |
Correct |
460 ms |
148112 KB |
Output is correct |
35 |
Correct |
745 ms |
153460 KB |
Output is correct |
36 |
Correct |
444 ms |
131984 KB |
Output is correct |
37 |
Correct |
183 ms |
88168 KB |
Output is correct |
38 |
Correct |
293 ms |
98220 KB |
Output is correct |
39 |
Correct |
1002 ms |
163172 KB |
Output is correct |
40 |
Correct |
903 ms |
154344 KB |
Output is correct |
41 |
Correct |
187 ms |
89404 KB |
Output is correct |
42 |
Correct |
434 ms |
110956 KB |
Output is correct |
43 |
Correct |
806 ms |
152752 KB |
Output is correct |
44 |
Correct |
435 ms |
148080 KB |
Output is correct |
45 |
Correct |
717 ms |
153464 KB |
Output is correct |
46 |
Correct |
447 ms |
132044 KB |
Output is correct |
47 |
Correct |
176 ms |
85788 KB |
Output is correct |
48 |
Correct |
314 ms |
101584 KB |
Output is correct |
49 |
Correct |
756 ms |
154400 KB |
Output is correct |
50 |
Correct |
658 ms |
151840 KB |
Output is correct |
51 |
Correct |
755 ms |
157944 KB |
Output is correct |
52 |
Correct |
989 ms |
163144 KB |
Output is correct |
53 |
Correct |
895 ms |
154348 KB |
Output is correct |
54 |
Correct |
210 ms |
89512 KB |
Output is correct |
55 |
Correct |
387 ms |
110968 KB |
Output is correct |
56 |
Correct |
819 ms |
152724 KB |
Output is correct |
57 |
Correct |
458 ms |
148140 KB |
Output is correct |
58 |
Correct |
719 ms |
153464 KB |
Output is correct |
59 |
Correct |
443 ms |
131912 KB |
Output is correct |
60 |
Correct |
178 ms |
85804 KB |
Output is correct |
61 |
Correct |
316 ms |
101568 KB |
Output is correct |
62 |
Correct |
762 ms |
154488 KB |
Output is correct |
63 |
Correct |
668 ms |
151856 KB |
Output is correct |
64 |
Correct |
732 ms |
157968 KB |
Output is correct |
65 |
Correct |
954 ms |
142460 KB |
Output is correct |
66 |
Correct |
1603 ms |
189304 KB |
Output is correct |
67 |
Correct |
1539 ms |
186932 KB |
Output is correct |
68 |
Correct |
1240 ms |
162064 KB |
Output is correct |
69 |
Correct |
1240 ms |
156952 KB |
Output is correct |
70 |
Correct |
120 ms |
79016 KB |
Output is correct |
71 |
Correct |
1510 ms |
189216 KB |
Output is correct |
72 |
Correct |
1542 ms |
186500 KB |
Output is correct |
73 |
Correct |
1255 ms |
161940 KB |
Output is correct |
74 |
Correct |
1558 ms |
182504 KB |
Output is correct |
75 |
Correct |
1405 ms |
189172 KB |
Output is correct |
76 |
Correct |
1405 ms |
186504 KB |
Output is correct |
77 |
Correct |
1178 ms |
161928 KB |
Output is correct |
78 |
Correct |
1146 ms |
163264 KB |
Output is correct |
79 |
Correct |
1363 ms |
166448 KB |
Output is correct |
80 |
Correct |
1306 ms |
157652 KB |
Output is correct |
81 |
Correct |
467 ms |
92804 KB |
Output is correct |
82 |
Correct |
650 ms |
114396 KB |
Output is correct |
83 |
Correct |
1093 ms |
156184 KB |
Output is correct |
84 |
Correct |
705 ms |
151624 KB |
Output is correct |
85 |
Correct |
1066 ms |
157052 KB |
Output is correct |
86 |
Correct |
729 ms |
135548 KB |
Output is correct |
87 |
Correct |
323 ms |
89280 KB |
Output is correct |
88 |
Correct |
490 ms |
105156 KB |
Output is correct |
89 |
Correct |
924 ms |
157884 KB |
Output is correct |
90 |
Correct |
1020 ms |
155548 KB |
Output is correct |
91 |
Correct |
941 ms |
161456 KB |
Output is correct |