#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
struct pt{ int x,y;pt(){}pt(int a, int b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
bool operator == (pt a, pt b){ return mp(a.x,a.y)==mp(b.x,b.y);}
vector<pt> v[4];
void Add(pt p)
{
v[0].pb(p);
v[1].pb(p);v[1].pb(p-pt(1,0));
v[2].pb(p);v[2].pb(p-pt(0,1));
v[3].pb(p);v[3].pb(p-pt(1,0));v[3].pb(p-pt(0,1));v[3].pb(p-pt(1,1));
}
void ckmn(int &a, int b){ a=min(a,b);}
void ckmx(int &a, int b){ a=max(a,b);}
const int N=200050;
const int M=900050;
const int H=20*M;
int ls[H],rs[H],tsz,sum[H],n,m;
struct PersistentSegmentTree
{
int root[N];
PersistentSegmentTree(){}
void Set(int p, int &c, int ss, int se, int qi)
{
c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+1;
if(ss==se) return;
int mid=ss+se>>1;
if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi);
else Set(rs[p],rs[c],mid+1,se,qi);
}
void Set(int p, int c, int qi){ Set(root[p],root[c],1,N,qi);}
int Get(int p, int c, int ss, int se, int qs, int qe)
{
if(qs>qe || qs>se || ss>qe) return 0;
if(qs<=ss && qe>=se) return sum[c]-sum[p];
int mid=ss+se>>1;
return Get(ls[p],ls[c],ss,mid,qs,qe)+Get(rs[p],rs[c],mid+1,se,qs,qe);
}
ll Get(int x1, int y1, int x2, int y2){ return (ll)(x2-x1+1)*(y2-y1+1)-Get(root[x1-1],root[x2],1,N,y1,y2);}
void Upd(int p, int c){ root[c]=root[p];}
} ST[4];
void Build()
{
for(int i=0;i<4;i++)
{
sort(v[i].begin(),v[i].end());
v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
for(int j=1,k=0;j<N;j++)
{
ST[i].Upd(j-1,j);
for(;k<v[i].size() && v[i][k].x==j;k++) ST[i].Set(j,j,v[i][k].y);
}
}
}
pt mn,mx;
void init(int R, int C, int sr, int sc, int M, char *S)
{
n=R,m=C;
pt pos(sr,sc);
Add(pos);
mn=mx=pos;
for(int i=0;i<M;i++)
{
if(S[i]=='N') pos.x--;
if(S[i]=='S') pos.x++;
if(S[i]=='W') pos.y--;
if(S[i]=='E') pos.y++;
Add(pos);
ckmn(mn.x,pos.x);ckmn(mn.y,pos.y);
ckmx(mx.x,pos.x);ckmx(mx.y,pos.y);
}
Build();
}
int colour(int x1, int y1, int x2, int y2)
{
ll ans=ST[0].Get(x1,y1,x2,y2)-ST[1].Get(x1,y1,x2-1,y2)-ST[2].Get(x1,y1,x2,y2-1)+ST[3].Get(x1,y1,x2-1,y2-1);
if(x1<mn.x && y1<mn.y && x2>mx.x && y2>mx.y) ans++;
return ans;
}
Compilation message
rainbow.cpp: In member function 'void PersistentSegmentTree::Set(int, int&, int, int, int)':
rainbow.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
rainbow.cpp: In member function 'int PersistentSegmentTree::Get(int, int, int, int, int, int)':
rainbow.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
rainbow.cpp: In function 'void Build()':
rainbow.cpp:57:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;k<v[i].size() && v[i][k].x==j;k++) ST[i].Set(j,j,v[i][k].y);
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
269 ms |
143064 KB |
Output is correct |
| 3 |
Correct |
242 ms |
145400 KB |
Output is correct |
| 4 |
Incorrect |
129 ms |
66248 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
