Submission #769340

#TimeUsernameProblemLanguageResultExecution timeMemory
769340BaytoroSeats (IOI18_seats)C++17
5 / 100
4067 ms64864 KiB
#include "seats.h" //#include "grader.cpp" #include <bits/stdc++.h> #define fr first #define sc second using namespace std; const int N=3e6+5; const int INF=1e9+5; pair<int,int> A[N]; struct node{ int mxx, mnx, mxy,mny; }; node tree[N]; node combine(node a, node b){ return {max(a.mxx,b.mxx),min(a.mnx,b.mnx),max(a.mxy,b.mxy),min(a.mny,b.mny)}; } void build(int x, int l, int r, vector<pair<int,int>> &vec){ if(l==r){ tree[x]={vec[l].fr,vec[l].fr,vec[l].sc,vec[l].sc}; return; } int md=(l+r)/2; build(2*x,l,md,vec); build(2*x+1,md+1,r,vec); tree[x]=combine(tree[2*x],tree[2*x+1]); } void update(int x, int l, int r, int i, pair<int,int> val){ if(l==r){ tree[x]={val.fr,val.fr,val.sc,val.sc}; return; } int md=(l+r)/2; if(i<=md) update(2*x ,l ,md,i,val); else update(2*x+1,md+1,r ,i,val); tree[x]=combine(tree[2*x],tree[2*x+1]); } int find_minx(int x, int l, int r, int lx, int rx){ if(l>rx || r<lx) return INF; if(lx<=l && r<=rx) return tree[x].mnx; int md=(l+r)/2; //cout<<l<<' '<<r<<' '<<lx<<' '<<rx<<endl; return min(find_minx(2*x,l,md,lx,rx),find_minx(2*x+1,md+1,r,lx,rx)); } int find_maxx(int x, int l, int r, int lx, int rx){ if(l>rx || r<lx) return -INF; if(lx<=l && r<=rx) return tree[x].mxx; int md=(l+r)/2; return max(find_maxx(2*x,l,md,lx,rx),find_maxx(2*x+1,md+1,r,lx,rx)); } int find_miny(int x, int l, int r, int lx, int rx){ if(l>rx || r<lx) return INF; if(lx<=l && r<=rx) return tree[x].mny; int md=(l+r)/2; return min(find_miny(2*x,l,md,lx,rx),find_miny(2*x+1,md+1,r,lx,rx)); } int find_maxy(int x, int l, int r, int lx, int rx){ if(l>rx || r<lx) return -INF; if(lx<=l && r<=rx) return tree[x].mxy; int md=(l+r)/2; return max(find_maxy(2*x,l,md,lx,rx),find_maxy(2*x+1,md+1,r,lx,rx)); } int k; int h,w; vector<int> R,C; void give_initial_chart(int H, int W, vector<int> r, vector<int> c) { R=r,C=c; h=H,w=W; int n=1; while(n<H*W) n*=2; vector<pair<int,int>> v(n); for(int i=0;i<H*W;i++) v[i]={R[i],C[i]}; k=n; build(1,0,k-1,v); } int swap_seats(int a, int b) { update(1,0,k-1,a,{R[b],C[b]}); update(1,0,k-1,b,{R[a],C[a]}); swap(R[a],R[b]); swap(C[a],C[b]); int id=1,ans=1; while(id<h*w){ int l=find_minx(1,0,k-1,0,id); int r=find_maxx(1,0,k-1,0,id); int d=find_miny(1,0,k-1,0,id); int u=find_maxy(1,0,k-1,0,id); //cout<<R[0]<<' '<<C[0]<<endl; //cout<<l<<' '<<r<<' '<<d<<' '<<u<<' '; //cout<<id<<endl; if((r-l+1)*(u-d+1)-1==id) ans++,id++; else id=(r-l+1)*(u-d+1)-1; } return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...