#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;
int tt;
struct MERGE_SORT_TREE {
struct NODE {
int st, fin;
int l, r;
vector<int> vc;
};
vector<NODE> tree;
void newNode(int a, int b) {
NODE temp;
temp.st=a;
temp.fin=b;
temp.l=temp.r=0;
tree.pb(temp);
//printf("%d\n", tree.size());
tt=tree.size();
}
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;
//printf("%d %d %d %d\n", tree[point].l, tree[point].r, tree[point].st, tree[point].fin);
if(!tree[point].l)newNode(tree[point].st, mid), tree[point].l=tt-1;
if(!tree[point].r)newNode(mid+1, tree[point].fin), tree[point].r=tt-1;
//printf("%d %d %d %d\n", tree[point].l, tree[point].r, tree[point].st, tree[point].fin);
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);
}
int 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, 300000);}
void update(int num, int p){
in_DST(0, num, p);
}
int get_sum(int xl, int xr, int yl, int yr){
if(xl>xr||yl>yr)return 0;
return sumrange(0, xl, xr, yl, yr);
}
};
MERGE_SORT_TREE 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;
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++;
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<a.size(); i++)seg.update(a[i].x, a[i].y);
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 br, int ac, 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)+2*(bc-br+1+ac-ar+1);
int temp=seg.get_sum(ar, ac, br, bc);
//printf("v=%d e=%d f=%d\n", v, e, temp);
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+2-temp;
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<a.size(); i++)seg.update(a[i].x, a[i].y);
~^~~~~~~~~
rainbow.cpp:89: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 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
1984 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
