제출 #299768

#제출 시각아이디문제언어결과실행 시간메모리
299768TMJN자리 배치 (IOI18_seats)C++17
5 / 100
4050 ms56472 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include "seats.h" #include <bits/stdc++.h> using namespace std; int H,W; pair<int,int>XY[1000000]; int treeXmin[1<<21],treeXmax[1<<21],treeYmin[1<<21],treeYmax[1<<21]; inline int calcXmin(int l,int r){ int a=H; l+=(1<<20); r+=(1<<20); while(l<=r){ if(a<treeXmin[l]&&a<treeXmin[r]){ } else if(treeXmin[l]<treeXmin[r]){ a=treeXmin[l]; } else{ a=treeXmin[r]; } l=(l+1)/2; r=(r-1)/2; } return a; } inline int calcXmax(int l,int r){ int a=0; l+=(1<<20); r+=(1<<20); while(l<=r){ if(a>treeXmax[l]&&a>treeXmax[r]){ } else if(treeXmax[l]>treeXmax[r]){ a=treeXmax[l]; } else{ a=treeXmax[r]; } l=(l+1)/2; r=(r-1)/2; } return a; } inline int calcYmin(int l,int r){ int a=W; l+=(1<<20); r+=(1<<20); while(l<=r){ if(a<treeYmin[l]&&a<treeYmin[r]){ } else if(treeYmin[l]<treeYmin[r]){ a=treeYmin[l]; } else{ a=treeYmin[r]; } l=(l+1)/2; r=(r-1)/2; } return a; } inline int calcYmax(int l,int r){ int a=0; l+=(1<<20); r+=(1<<20); while(l<=r){ if(a>treeYmax[l]&&a>treeYmax[r]){ } else if(treeYmax[l]>treeYmax[r]){ a=treeYmax[l]; } else{ a=treeYmax[r]; } l=(l+1)/2; r=(r-1)/2; } return a; } inline int next(int t,int a,int b,int c,int d){ int k=t+(1<<20); while(a<=treeXmin[k]&&treeXmax[k]<=b&&c<=treeYmin[k]&&treeYmax[k]<=d&&k!=1){ k=(k+1)/2; } while(k<(1<<20)){ if(treeXmin[k+k]<a||b<treeXmax[k+k]||treeYmin[k+k]<c||d<treeYmax[k+k]){ 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[i]={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--){ if(treeXmin[i+i]<treeXmin[i+i+1]){ treeXmin[i]=treeXmin[i+i]; } else{ treeXmin[i]=treeXmin[i+i+1]; } if(treeXmax[i+i]>treeXmax[i+i+1]){ treeXmax[i]=treeXmax[i+i]; } else{ treeXmax[i]=treeXmax[i+i+1]; } if(treeYmin[i+i]<treeYmin[i+i+1]){ treeYmin[i]=treeYmin[i+i]; } else{ treeYmin[i]=treeYmin[i+i+1]; } if(treeYmax[i+i]>treeYmax[i+i+1]){ treeYmax[i]=treeYmax[i+i]; } else{ treeYmax[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){ int p,q,r,s; p=calcXmax(0,t); q=calcXmin(0,t); r=calcYmax(0,t); s=calcYmin(0,t); if((p-q+1)*(r-s+1)==t+1){ res++; } t=max(t+1,next(t,q,p,s,r)-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...