Submission #1263264

#TimeUsernameProblemLanguageResultExecution timeMemory
1263264damoonLand of the Rainbow Gold (APIO17_rainbow)C++20
0 / 100
581 ms613200 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define all(x) x.begin(),x.end() #define unicorn(x) x.resize(unique(all(x))-x.begin()) typedef pair<int,int> pii; #define f first #define s second string pr(vector<pii> vv){for(auto [x,y]:vv)cout<<"("<<x<<","<<y<<") ";return"";} string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return"";} const int L=2e5+10, inf=1e9+10; int MA; int xmx=-inf, xmn=inf, ymx=-inf, ymn=inf; vector<pii> P; struct RC{ struct node{ int l,r,mid,sum; node* lc; node* rc; node(int l2, int r2){ l = l2; r = r2; lc = nullptr; rc = nullptr; mid = (l+r)/2; sum = 0; } void spread(){ if(lc == nullptr){ lc = new node(l,mid); rc = new node(mid,r); } } void update(int ind,int x,node* newnode){ if(l+1 == r){ newnode->sum = sum; newnode->sum += x; return; } spread(); if(ind < mid){ newnode->rc = rc; newnode->lc = new node(l,mid); lc->update(ind,x,newnode->lc); } else{ newnode->lc = lc; newnode->rc = new node(mid,r); rc->update(ind,x,newnode->rc); } newnode->sum = newnode->lc->sum + newnode->rc->sum; } int get(int l2,int r2){ if(l==l2 and r==r2) return sum; int ans = 0; spread(); if(l2 < mid) ans += lc->get(l2,min(r2,mid)); if(r2 > mid) ans += rc->get(max(l2,mid),r2); return ans; } }; node* R[L]; vector<int> good[L]; void add(int x,int y){ good[x].pb(y); } void build(){ R[L-1] = new node(1,L); for(int i=L-2;i>=1;i--){ R[i] = R[i+1]; sort(all(good[i])); unicorn(good[i]); for(auto x:good[i]){ node* rt = new node(1,L); R[i]->update(x,1,rt); R[i] = rt; } } } int get(int x,int y){ return R[x]->get(y,L); } }oo,ot,to,tt; void init(int A,int B,int sx,int sy,int N,char* S){ P.pb(pii(sx,sy)); for(int i=0;i<N;i++){ char c = S[i]; if(c == 'N') sx--; if(c == 'S') sx++; if(c == 'W') sy--; if(c == 'E') sy++; P.pb(pii(sx,sy)); } sort(all(P)); unicorn(P); map<pii,bool> is; for(auto [x,y]:P){ //oo oo.add(x,y); //ot ot.add(x,y); ot.add(x,y-1); //to to.add(x,y); to.add(x-1,y); //tt tt.add(x,y); tt.add(x-1,y); tt.add(x,y-1); tt.add(x-1,y-1); is[pii(x,y)] = 1; xmx = max(xmx , x); ymx = max(ymx , y); xmn = min(xmn , x); ymn = min(ymn , y); } oo.build(); ot.build(); to.build(); tt.build(); if(xmx!=A and xmn!=1 and ymx!=B and ymn!=1){ MA = 0; for(auto [x,y]:P){ MA += is[pii(x+1,y)]; MA += is[pii(x,y+1)]; MA += is[pii(x-1,y)]; MA += is[pii(x,y-1)]; } MA /= 2; MA = MA - P.size() + 2; for(auto [x,y]:P){ MA -= (is[pii(x+1,y)] and is[pii(x,y+1)] and is[pii(x+1,y+1)]); } } /* cout<<"P: "<<pr(P)<<endl; cout<<"ymx: "<<ymx<<endl; */ } ll get(int x1,int y1,int x2,int y2, RC &X){ if(x2 <= x1 or y2 <= y1) return 0; ll ans = (x2-x1)*(y2-y1); ans -= X.get(x1,y1); ans -= X.get(x2,y2); ans += X.get(x1,y2); ans += X.get(x2,y1); return ans; } int colour(int x1,int y1,int x2,int y2){ if(x1<xmn and x2>xmx and y1<ymn and y2>ymx) return MA; x2++; y2++; //cout<<"oo: "<<get(x1,y1,x2,y2,oo)<<" / ot: "<<get(x1,y1,x2,y2-1,ot)<<" / to: "<<get(x1,y1,x2-1,y2,to)<<" / tt: "<<get(x1,y1,x2-1,y2-1,tt)<<endl; return get(x1,y1,x2,y2,oo) - get(x1,y1,x2,y2-1,ot) - get(x1,y1,x2-1,y2,to) + get(x1,y1,x2-1,y2-1,tt); } /* int main(){ //ifstream cin ("in.in"); int X,Y,sx,sy,N,q; string inp; char I[100]; cin>>X>>Y>>N>>q; cin>>sx>>sy; cin>>inp; for(int i=0;i<N;i++){ I[i] = inp[i]; } init(X,Y,sx,sy,N,I); for(int i=1;i<=q;i++){ int x1,x2,y1,y2; cin >> x1 >> y1 >> x2 >> y2; cout<<colour(x1,y1,x2,y2)<<endl; } } */
#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...