#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
template<class B, class T>
struct fenwick_tree_2d_sparse_sum{
vector<B> X;
vector<vector<array<B, 2>>> Y;
vector<vector<T>> data;
fenwick_tree_2d_sparse_sum() {}
// O(n * log^2(n))
fenwick_tree_2d_sparse_sum(vector<pair<array<B, 2>, T>> init): X(init.size()){
sort(init.begin(), init.end());
for(auto i = 0; i < (int)init.size(); ++ i) X[i] = init[i].first[0];
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
int n = (int)X.size();
Y.resize(n);
data.resize(n);
vector<vector<pair<array<B, 2>, T>>> hold(n);
for(auto i = 0, x = 0; i < (int)init.size(); ++ i){
auto [pos, val] = init[i];
while(X[x] < pos[0]) ++ x;
hold[x].push_back({{pos[1], pos[0]}, val});
}
for(auto x = 1; x <= n; ++ x) if(x + (x & -x) <= n){
auto &hold0 = hold[x + (x & -x) - 1];
auto &hold1 = hold[x - 1];
int size = (int)hold0.size();
hold0.insert(hold0.end(), hold1.begin(), hold1.end());
}
for(auto x = 0; x < n; ++ x){
auto &Y0 = Y[x];
auto &hold0 = hold[x];
auto &data0 = data[x];
sort(hold0.begin(), hold0.end());
Y0.resize(hold0.size());
for(auto j = 0; j < (int)hold0.size(); ++ j) Y0[j] = hold0[j].first;
Y0.erase(unique(Y0.begin(), Y0.end()), Y0.end());
data0.resize(Y0.size());
for(auto j = 0, y = 0; j < (int)hold0.size(); ++ j){
while(Y0[y] < hold0[j].first) ++ y;
data0[y] += hold0[j].second;
}
int m = (int)data0.size();
for(auto y = 1; y <= m; ++ y) if(y + (y & -y) <= m) data0[y + (y & -y) - 1] += data0[y - 1];
}
}
// O(log^2(n))
void update(B _p, B _q, T x){
int p = lower_bound(X.begin(), X.end(), _p) - X.begin();
assert(p < (int)X.size() && X[p] == _p);
for(auto i = p + 1; i <= (int)X.size(); i += i & -i){
auto &Y0 = Y[i - 1];
auto &data0 = data[i - 1];
int q = lower_bound(Y0.begin(), Y0.end(), array{_q, _p}) - Y0.begin();
assert(q < (int)Y0.size() && Y0[q][0] == _q && Y0[q][1] == _p);
for(auto j = q + 1; j <= (int)data0.size(); j += j & -j) data0[j - 1] += x;
}
}
// O(log^2(n))
T prefix(B _xr, B _yr) const{
int xr = lower_bound(X.begin(), X.end(), _xr) - X.begin();
T res = 0;
for(auto i = xr; i > 0; i -= i & -i){
auto &Y0 = Y[i - 1];
auto &data0 = data[i - 1];
int yr = lower_bound(Y0.begin(), Y0.end(), array{_yr, numeric_limits<B>::min()}) - Y0.begin();
for(auto j = yr; j > 0; j -= j & -j) res += data0[j - 1];
}
return res;
}
// O(log^2(n))
T query(B _xl, B _yl, B _xr, B _yr) const{
if (_xl > _xr) return 0;
if (_yl > _yr) return 0;
return prefix(_xr, _yr) - prefix(_xl, _yr) - prefix(_xr, _yl) + prefix(_xl, _yl);
}
// O(log^2(n))
T query(B _x, B _y) const{
return prefix(_x + 1, _y + 1) - prefix(_x + 1, _y) - prefix(_x, _y + 1) + prefix(_x, _y);
}
};
template<class T>
void compress(vector<T> &a) {
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
}
vector<pair<array<int, 2>, int>> vertex;
vector<pair<array<int, 2>, int>> col_edge;
vector<pair<array<int, 2>, int>> row_edge;
vector<pair<array<int, 2>, int>> river;
fenwick_tree_2d_sparse_sum<int, int> fw_vertex, fw_col_edge, fw_row_edge, fw_river;
void add_cell(int x, int y) {
river.push_back({{x, y}, 1});
vertex.push_back({{x, y}, 1});
vertex.push_back({{x + 1, y}, 1});
vertex.push_back({{x, y + 1}, 1});
vertex.push_back({{x + 1, y + 1}, 1});
col_edge.push_back({{x, y}, 1});
col_edge.push_back({{x, y + 1}, 1});
row_edge.push_back({{x, y}, 1});
row_edge.push_back({{x + 1, y}, 1});
}
void init(int R, int C, int sr, int sc, int M, char *S) {
--sr, --sc;
add_cell(sr, sc);
for (int i = 0; i < M; ++i) {
if (S[i] == 'N') --sr;
if (S[i] == 'S') ++sr;
if (S[i] == 'E') ++sc;
if (S[i] == 'W') --sc;
add_cell(sr, sc);
}
compress(vertex);
compress(col_edge);
compress(row_edge);
compress(river);
fw_vertex = fenwick_tree_2d_sparse_sum(vertex);
fw_col_edge = fenwick_tree_2d_sparse_sum(col_edge);
fw_row_edge = fenwick_tree_2d_sparse_sum(row_edge);
fw_river = fenwick_tree_2d_sparse_sum(river);
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac;
int V = 2 * (br - ar) + 2 * (bc - ac) + fw_vertex.query(ar + 1, ac + 1, br, bc);
// cout << "V: " << V << endl;
int E = 2 * (br - ar) + 2 * (bc - ac) + fw_col_edge.query(ar, ac + 1, br, bc) + fw_row_edge.query(ar + 1, ac, br, bc);
// cout << "E: " << E << endl;
int R = fw_river.query(ar, ac, br, bc);
// cout << "R: " << R << endl;
return E - V + 1 - R;
}
Compilation message
rainbow.cpp: In instantiation of 'fenwick_tree_2d_sparse_sum<B, T>::fenwick_tree_2d_sparse_sum(std::vector<std::pair<std::array<B, 2>, T> >) [with B = int; T = int]':
rainbow.cpp:129:50: required from here
rainbow.cpp:29:17: warning: unused variable 'size' [-Wunused-variable]
29 | int size = (int)hold0.size();
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
436 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
245 ms |
19600 KB |
Output is correct |
| 4 |
Correct |
368 ms |
30408 KB |
Output is correct |
| 5 |
Correct |
362 ms |
32544 KB |
Output is correct |
| 6 |
Correct |
325 ms |
27116 KB |
Output is correct |
| 7 |
Correct |
368 ms |
28880 KB |
Output is correct |
| 8 |
Correct |
152 ms |
19388 KB |
Output is correct |
| 9 |
Correct |
354 ms |
32036 KB |
Output is correct |
| 10 |
Correct |
361 ms |
32240 KB |
Output is correct |
| 11 |
Correct |
317 ms |
27832 KB |
Output is correct |
| 12 |
Correct |
250 ms |
29940 KB |
Output is correct |
| 13 |
Correct |
257 ms |
31216 KB |
Output is correct |
| 14 |
Correct |
269 ms |
30820 KB |
Output is correct |
| 15 |
Correct |
264 ms |
27224 KB |
Output is correct |
| 16 |
Correct |
283 ms |
25324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
221 ms |
29668 KB |
Output is correct |
| 3 |
Correct |
600 ms |
126964 KB |
Output is correct |
| 4 |
Correct |
651 ms |
101320 KB |
Output is correct |
| 5 |
Correct |
577 ms |
102760 KB |
Output is correct |
| 6 |
Correct |
162 ms |
21748 KB |
Output is correct |
| 7 |
Incorrect |
217 ms |
29412 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
436 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
436 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
