#include "rainbow.h"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int ans[1<<17];
struct seg {
struct node {
int sum = 0;
node *l = 0, *r = 0;
};
node *rt;
int n;
seg(int N = 0) : rt(new node()), n(N) {}
void update(node*& v, int l, int r, int p) {
if(p < l || r < p) return;
if(!v) v = new node();
v->sum++;
if(l == r) return;
int mid = (l+r)/2;
update(v->l, l, mid, p);
update(v->r, mid+1, r, p);
}
int query(node *v, int l, int r, int ql, int qr) {
if(!v || r < ql || qr < l) return 0;
if(ql <= l && r <= qr) return v->sum;
int mid = (l+r)/2;
return query(v->l, l, mid, ql, qr) + query(v->r, mid+1, r, ql, qr);
}
void update(int p) { update(rt, 1, n, p); }
int query(int ql, int qr) { return query(rt, 1, n, ql, qr); }
};
struct rect_query_online {
vector<seg> st;
int n;
rect_query_online(int n = 0, int m = 0) : n(n), st(n+1) {
for(int i = 1; i <= n; i++) st[i] = seg(m);
}
void add_point(int x, int y) {
for(; x <= n; x += x&-x) st[x].update(y);
}
int query(int x, int yl, int yr) {
int ans = 0;
//cout << x << " " << yl << " " << yr << ": " << endl;
for(; x; x -= x&-x) ans += st[x].query(yl, yr);
//cout << ans << endl;
return ans;
}
int query(int xl, int xr, int yl, int yr) {
if(xl > xr || yl > yr) return 0;
return query(xr, yl, yr) - query(xl-1, yl, yr);
}
};
using pt = array<int, 2>;
int n, m;//segments are identified by their top left point
map<pt, int> points, segx, segy;
set<pt> marked;
void add_block(int x, int y) {
if(!marked.insert({x, y}).second) return;
points[{x, y}]++;
points[{x+1, y}]++;
points[{x, y+1}]++;
points[{x+1, y+1}]++;
segx[{x, y}]++;
segx[{x, y+1}]++;
segy[{x, y}]++;
segy[{x+1, y}]++;
}
rect_query_online rp, rb, rx, ry;
int minx = 1<<30, miny = 1<<30, maxy = -1, maxx = -1;
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R+1, m = C+1;
add_block(sr, sc);
minx = maxx = sr, miny = maxy = sc;
for(int i = 0; i < M; i++) {
if(S[i] == 'N') sr--;
if(S[i] == 'S') sr++;
if(S[i] == 'W') sc--;
if(S[i] == 'E') sc++;
add_block(sr, sc);
minx = min(minx, sr);
maxx = max(maxx, sr);
miny = min(miny, sc);
maxy = max(maxy, sc);
}
rp = rect_query_online(n, m);
rx = rect_query_online(n, m);
ry = rect_query_online(n, m);
rb = rect_query_online(n, m);
for(auto i : points) if(i.second < 4) {
rp.add_point(i.first[0], i.first[1]);
}
for(auto i : segx) {
rx.add_point(i.first[0], i.first[1]);
}
for(auto i : segy) {
ry.add_point(i.first[0], i.first[1]);
}
for(auto i : marked) {
rb.add_point(i[0], i[1]);
}
}
int colour(int xl, int yl, int xr, int yr) {
xr++, yr++;
//cout << xl << " " << xr << " " << yl << " " << yr << endl;
int v, e, b;
v = e = 2*(xr+yr-xl-yl);
//cout << v << endl;
v += rp.query(xl+1, xr-1, yl+1, yr-1);
e += rx.query(xl, xr-1, yl+1, yr-1) + ry.query(xl+1, xr-1, yl, yr-1);
b = rb.query(xl, xr-1, yl, yr-1)+1;
int f = e-v+2-b;
f += xl < minx && maxx < xr && yl < miny && maxy < yr;
return f;
}
Compilation message
rainbow.cpp: In constructor 'rect_query_online::rect_query_online(int, int)':
rainbow.cpp:37:6: warning: 'rect_query_online::n' will be initialized after [-Wreorder]
37 | int n;
| ^
rainbow.cpp:36:14: warning: 'std::vector<seg> rect_query_online::st' [-Wreorder]
36 | vector<seg> st;
| ^~
rainbow.cpp:38:2: warning: when initialized here [-Wreorder]
38 | rect_query_online(int n = 0, int m = 0) : n(n), st(n+1) {
| ^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1560 ms |
362172 KB |
Output is correct |
| 3 |
Correct |
1332 ms |
331032 KB |
Output is correct |
| 4 |
Correct |
1456 ms |
352120 KB |
Output is correct |
| 5 |
Correct |
1057 ms |
274884 KB |
Output is correct |
| 6 |
Correct |
282 ms |
79084 KB |
Output is correct |
| 7 |
Incorrect |
421 ms |
92600 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
