Submission #132268

#TimeUsernameProblemLanguageResultExecution timeMemory
132268baluteshihLand of the Rainbow Gold (APIO17_rainbow)C++14
12 / 100
1185 ms420304 KiB
#include "rainbow.h" #pragma GCC optimize("O3") #include <bits/stdc++.h> #define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define pb push_back #define ET cout << "\n" #define ALL(v) v.begin(),v.end() #define MP make_pair #define F first #define S second #define MEM(i,j) memset(i,j,sizeof i) #define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;} using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; struct node { int data=0; node *l=0,*r=0; void up() { data=0; if(l) data+=l->data; if(r) data+=r->data; } }*root[400005]; node* modify(int x,int l,int r,node *p,int v) { if(!p) p=new node; else p=new node(*p); if(l==r) return p->data+=v,p; int m=l+r>>1; if(x<=m) p->l=modify(x,l,m,p->l,v); else p->r=modify(x,m+1,r,p->r,v); return p->up(),p; } node *lch(node *p){return p?p->l:0;} node *rch(node *p){return p?p->r:0;} int gdata(node *p){return p?p->data:0;} int query(int L,int R,int l,int r,node *p,node *q) { if(!p&&!q) return 0; if(L<=l && R>=r) return gdata(p)-gdata(q); int m=l+r>>1; if(R<=m) return query(L,R,l,m,lch(p),lch(q)); if(L>m) return query(L,R,m+1,r,rch(p),rch(q)); return query(L,R,l,m,lch(p),lch(q))+query(L,R,m+1,r,rch(p),rch(q)); } int MAXC; set<pii> s,dt,rl,cl; int num[256],dx[4]={-1,1,0,0},dy[4]={0,0,1,-1}; vector<pii> wei[400005]; void maintain(int x,int y) { s.insert(MP(x,y)); dt.insert(MP(x,y)),dt.insert(MP(x+1,y+1)),dt.insert(MP(x+1,y)),dt.insert(MP(x,y+1)); rl.insert(MP(x,y)),rl.insert(MP(x+1,y)); cl.insert(MP(x,y)),cl.insert(MP(x,y+1)); } void init(int R, int C, int sr, int sc, int M, char *S) { num['N']=0,num['S']=1,num['E']=2,num['W']=3,maintain(sr,sc),MAXC=2*C+1; for(int i=0;i<M;++i) sr+=dx[num[S[i]]],sc+=dy[num[S[i]]],maintain(sr,sc); for(auto i:s) wei[i.F*2].pb(MP(i.S*2,-1)); for(auto i:dt) wei[i.F*2-1].pb(MP(i.S*2-1,-1)); for(auto i:rl) wei[i.F*2-1].pb(MP(i.S*2,1)); for(auto i:cl) wei[i.F*2].pb(MP(i.S*2-1,1)); for(int i=1;i<=2*R+1;++i,root[i]=root[i-1]) for(auto j:wei[i]) root[i]=modify(j.F,1,MAXC,root[i],j.S); } int colour(int ar, int ac, int br, int bc) { return 1+query(ac*2,bc*2,1,MAXC,root[br*2],root[ar*2-1]); }

Compilation message (stderr)

rainbow.cpp: In function 'node* modify(int, int, int, node*, int)':
rainbow.cpp:36:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
rainbow.cpp: In function 'int query(int, int, int, int, node*, node*)':
rainbow.cpp:51:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:74:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   sr+=dx[num[S[i]]],sc+=dy[num[S[i]]],maintain(sr,sc);
                  ^
rainbow.cpp:74:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   sr+=dx[num[S[i]]],sc+=dy[num[S[i]]],maintain(sr,sc);
                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...