제출 #299715

#제출 시각아이디문제언어결과실행 시간메모리
299715TMJN자리 배치 (IOI18_seats)C++17
5 / 100
4066 ms60628 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; int H,W; vector<pair<int,int>>XY; int treeXmin[1<<21],treeXmax[1<<21],treeYmin[1<<21],treeYmax[1<<21]; int calcXmin(int l,int r){ int a=H; l+=(1<<20); r+=(1<<20); while(l<=r){ a=min({a,treeXmin[l],treeXmin[r]}); l=(l+1)/2; r=(r-1)/2; } return a; } int calcXmax(int l,int r){ int a=0; l+=(1<<20); r+=(1<<20); while(l<=r){ a=max({a,treeXmax[l],treeXmax[r]}); l=(l+1)/2; r=(r-1)/2; } return a; } int calcYmin(int l,int r){ int a=W; l+=(1<<20); r+=(1<<20); while(l<=r){ a=min({a,treeYmin[l],treeYmin[r]}); l=(l+1)/2; r=(r-1)/2; } return a; } int calcYmax(int l,int r){ int a=0; l+=(1<<20); r+=(1<<20); while(l<=r){ a=max({a,treeYmax[l],treeYmax[r]}); l=(l+1)/2; r=(r-1)/2; } return a; } int next_Xmin(int t){ int m=calcXmin(0,t); int k=t+(1<<20); while(m<=treeXmin[k]&&k!=1){ k=(k+1)/2; } while(k<(1<<20)){ if(treeXmin[k+k]<m){ k=k+k; } else{ k=k+k+1; } } return k-(1<<20); } int next_Xmax(int t){ int m=calcXmax(0,t); int k=t+(1<<20); while(m>=treeXmax[k]&&k!=1){ k=(k+1)/2; } while(k<(1<<20)){ if(treeXmax[k+k]>m){ k=k+k; } else{ k=k+k+1; } } return k-(1<<20); } int next_Ymin(int t){ int m=calcYmin(0,t); int k=t+(1<<20); while(m<=treeYmin[k]&&k!=1){ k=(k+1)/2; } while(k<(1<<20)){ if(treeYmin[k+k]<m){ k=k+k; } else{ k=k+k+1; } } return k-(1<<20); } int next_Ymax(int t){ int m=calcYmax(0,t); int k=t+(1<<20); while(m>=treeYmax[k]&&k!=1){ k=(k+1)/2; } while(k<(1<<20)){ if(treeYmax[k+k]>m){ k=k+k; } else{ k=k+k+1; } } return k-(1<<20); } void update(int x){ int t=x; x+=(1<<20); treeXmin[x]=treeXmax[x]=XY[t].first; treeYmin[x]=treeYmax[x]=XY[t].second; while(x){ x/=2; treeXmin[x]=min(treeXmin[x+x],treeXmin[x+x+1]); treeXmax[x]=max(treeXmax[x+x],treeXmax[x+x+1]); treeYmin[x]=min(treeYmin[x+x],treeYmin[x+x+1]); treeYmax[x]=max(treeYmax[x+x],treeYmax[x+x+1]); } } void give_initial_chart(int h,int w,vector<int>R,vector<int>C){ H=h; W=w; for(int i=0;i<H*W;i++){ XY.push_back({R[i],C[i]}); } for(int i=0;i<H*W;i++){ treeXmin[i+(1<<20)]=treeXmax[i+(1<<20)]=XY[i].first; treeYmin[i+(1<<20)]=treeYmax[i+(1<<20)]=XY[i].second; } treeXmin[H*W+(1<<20)]=treeYmin[H*W+(1<<20)]=-0xE869120; treeXmax[H*W+(1<<20)]=treeYmax[H*W+(1<<20)]=0xE869120; for(int i=(1<<20)-1;i;i--){ treeXmin[i]=min(treeXmin[i+i],treeXmin[i+i+1]); treeXmax[i]=max(treeXmax[i+i],treeXmax[i+i+1]); treeYmin[i]=min(treeYmin[i+i],treeYmin[i+i+1]); treeYmax[i]=max(treeYmax[i+i],treeYmax[i+i+1]); } } int swap_seats(int a,int b){ swap(XY[a],XY[b]); update(a); update(b); int res=0; int t=0; while(t<H*W){ if((calcXmax(0,t)-calcXmin(0,t)+1)*(calcYmax(0,t)-calcYmin(0,t)+1)==t+1){ res++; } t=max(t+1,min({next_Xmin(t),next_Xmax(t),next_Ymin(t),next_Ymax(t)})-1); } return res; }
#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...