Submission #98319

#TimeUsernameProblemLanguageResultExecution timeMemory
98319fefeSeats (IOI18_seats)C++17
17 / 100
4099 ms181908 KiB
#include "seats.h" #include<bits/stdc++.h> #define MAX_N 1000005 #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second using namespace std; typedef pair<int,int> pii; int h,w,ans; std::vector<int> r; pii V[MAX_N]; pii mx[MAX_N],mi[MAX_N]; vector<int> lst; struct inout_pq{ priority_queue<int> in,out; void add(int x){in.push(-x);} void delect(int x){out.push(-x);} int return_top(){ while(in.size() && out.size() && in.top()==out.top()){in.pop(),out.pop();} if(in.size()) return -in.top(); return 0; } }X[MAX_N],Y[MAX_N]; int sp(int a,int b){ pii x,y; swap(V[a],V[b]); if(a>b) swap(a,b); a=a?a:a+1; mx[0]=mi[0]=V[0]; for(int i=a;i<=b;i++){ ans-=((mx[i].fi-mi[i].fi+1)*(mx[i].se-mi[i].se+1)==(i+1))?1:0; mx[i].fi=max(mx[i-1].fi,V[i].fi);mx[i].se=max(mx[i-1].se,V[i].se); mi[i].fi=min(mi[i-1].fi,V[i].fi);mi[i].se=min(mi[i-1].se,V[i].se); ans+=((mx[i].fi-mi[i].fi+1)*(mx[i].se-mi[i].se+1)==(i+1))?1:0; } return ans; } void sp_init(){ mx[0]=mi[0]=V[0]; swap(V[0],V[h*w-1]); ans=1; ans=sp(0,h*w-1); } void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { int i; h=H;w=W; for(i=0;i<H*W;i++) V[i]={R[i],C[i]}; if(h+w>=2000){sp_init();return;} for(i=0;i<H*W;i++){ X[R[i]].add(i); Y[C[i]].add(i); } } int swap_seats(int a, int b) { int i; if(h+w>=2000) return sp(a,b); X[V[a].fi].delect(a);Y[V[a].se].delect(a); X[V[b].fi].delect(b);Y[V[b].se].delect(b); swap(V[a],V[b]); X[V[a].fi].add(a);Y[V[a].se].add(a); X[V[b].fi].add(b);Y[V[b].se].add(b); lst.clear();lst.resize(0); for(i=0;i<h;i++) lst.pb(X[i].return_top()); for(i=0;i<w;i++) lst.pb(Y[i].return_top()); sort(all(lst));lst.erase(unique(all(lst)),lst.end()); pii x,y; ans=1; x={V[0].fi,V[0].fi};y={V[0].se,V[0].se}; for(int p:lst){ ans+=((x.se-x.fi+1)*(y.se-y.fi+1)==(p)); y.fi=min(y.fi,V[p].se);y.se=max(y.se,V[p].se); x.fi=min(x.fi,V[p].fi);x.se=max(x.se,V[p].fi); } 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...