제출 #299738

#제출 시각아이디문제언어결과실행 시간메모리
299738TMJN자리 배치 (IOI18_seats)C++17
5 / 100
4048 ms56056 KiB
#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]; 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(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--){ 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){ 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...