#include "rainbow.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(t) t.begin(), t.end()
using namespace std;
typedef long long LL;
struct MERGE_SORT_TREE {
struct NODE {
int st, fin;
vector<int> vc;
};
NODE tree[1000010];
int x;
void initt(int point, int num){
if(num==1){
x++;
tree[point].st=x;
tree[point].fin=x;
}
if(num<=1)return;
initt(point*2, num-num/2);
initt(point*2+1, num/2);
tree[point].st=tree[point*2].st;
tree[point].fin=tree[point*2+1].fin;
}
void in_MST(int point, int num, int p) {
tree[point].vc.pb(p);
if(tree[point].st==tree[point].fin)return;
int mid=(tree[point].st+tree[point].fin)/2;
if(num<=mid)in_MST(point*2, num, p);
else in_MST(point*2+1, num, p);
}
void relax(int point){
sort(all(tree[point].vc));
if(tree[point].st==tree[point].fin)return;
relax(point*2);
relax(point*2+1);
}
int sumrange(int point, int xl, int xr, int yl, int yr){
int ret;
if(tree[point].st>=xl&&tree[point].fin<=xr)
return ret=upper_bound(all(tree[point].vc), yr)-lower_bound(all(tree[point].vc), yl);
if(tree[point].st>xr||tree[point].fin<xl)return 0;
return sumrange(point*2, xl, xr, yl, yr)+sumrange(point*2+1, xl, xr, yl, yr);
}
MERGE_SORT_TREE(){x=0; initt(1, 200010);}
void update(LL num, LL p){
in_MST(1, (int)num, (int)p);
}
int get_sum(int xl, int yl, int xr, int yr){
if(xl>xr||yl>yr)return 0;
return sumrange(1, xl, xr, yl, yr);
}
};
MERGE_SORT_TREE segv, segdown, segright, segreal;
int n, m;
unordered_set<LL> s1, s2, s3, s4;
void inseg(int xx, int yy)
{
LL x=(LL)xx, y=(LL)yy;
if(!s1.count(300000*x+y)){
s1.insert(300000*x+y);
segv.update(x, y);
}
x++;
if(!s1.count(300000*x+y)){
s1.insert(300000*x+y);
segv.update(x, y);
}
x--;
y++;
if(!s1.count(300000*x+y)){
s1.insert(300000*x+y);
segv.update(x, y);
}
x++;
if(!s1.count(300000*x+y)){
s1.insert(300000*x+y);
segv.update(x, y);
}
x--;
y--;
if(!s2.count(300000*x+y)){
s2.insert(300000*x+y);
segdown.update(x, y);
}
y++;
if(!s2.count(300000*x+y)){
s2.insert(300000*x+y);
segdown.update(x, y);
}
y--;
if(!s3.count(300000*x+y)){
s3.insert(300000*x+y);
segright.update(x, y);
}
x++;
if(!s3.count(300000*x+y)){
s3.insert(300000*x+y);
segright.update(x, y);
}
x--;
if(!s4.count(300000*x+y)){
s4.insert(300000*x+y);
segreal.update(x, y);
}
}
void init(int R, int C, int sr, int sc, int M, char S[]){
n=R;
m=C;
inseg(sr, 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++;
inseg(sr, sc);
}
segreal.relax(1);
segv.relax(1);
segdown.relax(1);
segright.relax(1);
}
int colour(int xst, int yst, int xfin, int yfin){
int realv=segreal.get_sum(xst, yst, xfin, yfin);
int v=segv.get_sum(xst+1, yst+1, xfin, yfin)+2*(xfin-xst+yfin-yst+2);
int e=segdown.get_sum(xst+1, yst, xfin, yfin)+segright.get_sum(xst, yst+1, xfin, yfin)+2*(xfin-xst+yfin-yst+2);
int c;
if(!realv)c=1;
else if(segreal.get_sum(xst, yst, xst, yfin)||segreal.get_sum(xfin, yst, xfin, yfin)||segreal.get_sum(xst, yst, xfin, yst)||segreal.get_sum(xst, yfin, xfin, yfin))c=1;
else c=2;
return e-v+c-realv;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
125688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
125548 KB |
Output is correct |
| 2 |
Correct |
135 ms |
125816 KB |
Output is correct |
| 3 |
Incorrect |
638 ms |
173520 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
125704 KB |
Output is correct |
| 2 |
Incorrect |
681 ms |
197164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
125688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
125688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
