#include "rainbow.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(t) t.begin(), t.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
struct MERGE_SORT_TREE {
struct NODE {
int st, fin;
int l, r;
vector<int> vc;
};
vector<NODE> tree;
int newNode(int a, int b) {
NODE temp;
temp.st=a;
temp.fin=b;
temp.l=temp.r=0;
tree.push_back(temp);
return tree.size()-1;
}
void in_DST(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(!tree[point].l)tree[point].l=newNode(tree[point].st, mid);
if(!tree[point].r)tree[point].r=newNode(mid+1, tree[point].fin);
int da=tree[point].l;
if(num<=mid)in_DST(tree[point].l, num, p);
else in_DST(tree[point].r, num, p);
}
void relax(int point){
sort(all(tree[point].vc));
if(tree[point].l)relax(tree[point].l);
if(tree[point].r)relax(tree[point].r);
}
LL sumrange(int point, int xl, int xr, int yl, int yr){
if(tree[point].st>=xl&&tree[point].fin<=xr)
return upper_bound(all(tree[point].vc), yr)-lower_bound(all(tree[point].vc), yl);
if(tree[point].st>xl||tree[point].fin<xr)return 0;
return sumrange(tree[point].l, xl, xr, yl, yr)+sumrange(tree[point].r, xl, xr, yl, yr);
}
MERGE_SORT_TREE(){newNode(0, 10);}
void update(int num, int p){
in_DST(0, num, p);
}
LL get_sum(int xl, int xr, int yl, int yr){
return sumrange(0, xl, xr, yl, yr);
}
}seg, segdown, segright, segf;
int n, m;
unordered_set<LL> us;
vector<pii> a, b;
void invec(int x, int y)
{
a.pb(mp(x, y));
b.pb(mp(x, y));
b.pb(mp(x-1, y));
b.pb(mp(x, y-1));
b.pb(mp(x-1, y-1));
}
void init(int R, int C, int sr, int sc, int M, char S[]){
n=R;
m=C;
seg.update(sr, sc);
invec(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++;
seg.update(sr, sc);
invec(sr, sc);
}
sort(all(a));
sort(all(b));
a.erase(unique(all(a)), a.end());
b.erase(unique(all(b)), b.end());
for(int i=0; i<b.size(); i++){
int xx=b[i].x, yy=b[i].y;
segf.update(xx, yy);
if(binary_search(all(a), mp(xx, yy))||binary_search(all(a), mp(xx+1, yy)))segdown.update(xx, yy);
if(binary_search(all(a), mp(xx, yy))||binary_search(all(a), mp(xx, yy+1)))segright.update(xx, yy);
}
seg.relax(0);
segf.relax(0);
segdown.relax(0);
segright.relax(0);
}
int colour(int ar, int ac, int br, int bc) {
int v=segf.get_sum(ar, ac-1, br, bc-1)+2*(bc-br+1+ac-ar+1);
int e=segright.get_sum(ar, ac-1, br, bc)+segdown.get_sum(ar, ac, br, bc-1);
int temp=seg.get_sum(ar, ac, br, bc);
if(temp==0||seg.get_sum(ar, ar, br, bc)||seg.get_sum(ac, ac, br, bc)||seg.get_sum(ar, ac, br, br)||seg.get_sum(ar, ac, bc, bc))return e-v+1-temp;
return e-v+1-temp;
}
/*
6 4 9 4
3 3
NWESSWEWS
*/
Compilation message
rainbow.cpp: In member function 'void MERGE_SORT_TREE::in_DST(int, int, int)':
rainbow.cpp:33:13: warning: unused variable 'da' [-Wunused-variable]
int da=tree[point].l;
^~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<b.size(); i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
