#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, R, C;
set<pii> P;
struct Node{
int val=0;
int lc=0, rc=0;
};
struct PST{
int rt[202020], cnt=1;
Node T[4040404];
void update(int pre, int now, int s, int e, int t){
if (pre != now) T[now].val = T[pre].val;
T[now].val++;
if (s == e) return;
int mid = (s+e)/2;
if (t <= mid){
if (!T[now].lc) {
T[now].lc = cnt++;
T[now].rc = T[pre].rc;
}
update(T[pre].lc, T[now].lc, s, mid, t);
}
else{
if (!T[now].rc) {
T[now].rc = cnt++;
T[now].lc = T[pre].lc;
}
update(T[pre].rc, T[now].rc, mid+1, e, t);
}
}
int query(int now, int s, int e, int ts, int te){
if (e < ts || te < s || T[now].val == 0) return 0;
if (ts <= s && e <= te) return T[now].val;
int mid = (s+e)/2;
return query(T[now].lc, s, mid, ts, te)+query(T[now].rc, mid+1, e, ts, te);
}
} V, HE, VE, F;
void init(int _R, int _C, int sr, int sc, int _M, char *S) {
R = _R, C = _C, N = _M;
P.insert(pii(sr, sc));
for (int i=0; i<N; i++){
if (S[i] == 'N') sr--;
if (S[i] == 'S') sr++;
if (S[i] == 'W') sc--;
if (S[i] == 'E') sc++;
P.insert(pii(sr, sc));
}
int lr=0;
for (pii it : P){
for (int i=lr+1; i<it.first; i++){
V.rt[it.first] = V.rt[lr];
HE.rt[it.first] = HE.rt[lr];
VE.rt[it.first] = VE.rt[lr];
F.rt[it.first] = F.rt[lr];
}
if (!V.rt[it.first]) V.rt[it.first] = V.cnt++;
V.update(V.rt[it.first-1], V.rt[it.first], 1, C, it.second);
if (P.find(pii(it.first, it.second+1)) != P.end()){
if (!HE.rt[it.first]) HE.rt[it.first] = HE.cnt++;
HE.update(HE.rt[it.first-1], HE.rt[it.first], 1, C, it.second);
}
else if (!HE.rt[it.first]) HE.rt[it.first] = HE.rt[it.first-1];
if (P.find(pii(it.first+1, it.second)) != P.end()){
if (!VE.rt[it.first]) VE.rt[it.first] = VE.cnt++;
VE.update(VE.rt[it.first-1], VE.rt[it.first], 1, C, it.second);
}
else if (!VE.rt[it.first]) VE.rt[it.first] = VE.rt[it.first-1];
if (P.find(pii(it.first+1, it.second+1)) != P.end()
&& P.find(pii(it.first, it.second+1)) != P.end()
&& P.find(pii(it.first+1, it.second)) != P.end()){
if (!F.rt[it.first]) F.rt[it.first] = F.cnt++;
F.update(F.rt[it.first-1], F.rt[it.first], 1, C, it.second);
}
else if (!F.rt[it.first]) F.rt[it.first] = F.rt[it.first-1];
lr = it.first;
}
for (int i=lr+1; i<=R; i++){
V.rt[i] = V.rt[lr];
HE.rt[i] = HE.rt[lr];
VE.rt[i] = VE.rt[lr];
F.rt[i] = F.rt[lr];
}
}
int colour(int ar, int ac, int br, int bc) {
int ret = 1;
if (ar < br) ret += HE.query(HE.rt[br-1], 1, C, ac, bc-1) - HE.query(HE.rt[ar], 1, C, ac, bc-1);
ret += VE.query(VE.rt[br-1], 1, C, ac+1, bc-1) - VE.query(VE.rt[ar-1], 1, C, ac+1, bc-1);
ret += V.query(V.rt[ar], 1, C, ac, bc) - V.query(V.rt[ar-1], 1, C, ac, bc);
ret += V.query(V.rt[br], 1, C, ac, bc) - V.query(V.rt[br-1], 1, C, ac, bc);
ret += V.query(V.rt[br], 1, C, ac, ac) - V.query(V.rt[ar-1], 1, C, ac, ac);
ret += V.query(V.rt[br], 1, C, bc, bc) - V.query(V.rt[ar-1], 1, C, bc, bc);
ret -= V.query(V.rt[br], 1, C, ac, bc) - V.query(V.rt[ar-1], 1, C, ac, bc);
ret -= F.query(F.rt[br-1], 1, C, ac, bc-1) - F.query(F.rt[ar-1], 1, C, ac, bc-1);
if (P.find(pii(ar, ac)) != P.end()) ret--;
if (P.find(pii(ar, bc)) != P.end()) ret--;
if (P.find(pii(br, ac)) != P.end()) ret--;
if (P.find(pii(br, bc)) != P.end()) ret--;
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
190328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
190200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
190072 KB |
Output is correct |
| 2 |
Incorrect |
310 ms |
196628 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
190328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
190328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
