제출 #210551

#제출 시각아이디문제언어결과실행 시간메모리
210551medk자리 배치 (IOI18_seats)C++14
5 / 100
4094 ms102520 KiB
#include "seats.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define x first #define y second using namespace std; int H,W; vector<int> X,Y; vector<pair<pair<int,int>,pair<int,int>>> sgt; //X(min,max) Y(min,max) void build(int p=1, int l=0, int r=H*W-1) { if(l==r) { sgt[p]={{X[l],X[l]},{Y[l],Y[l]}}; return; } int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); sgt[p].x.x=min(sgt[p*2].x.x, sgt[p*2+1].x.x); sgt[p].y.x=min(sgt[p*2].y.x, sgt[p*2+1].y.x); sgt[p].x.y=max(sgt[p*2].x.y, sgt[p*2+1].x.y); sgt[p].y.y=max(sgt[p*2].y.y, sgt[p*2+1].y.y); } void update(int id, int p=1, int l=0, int r=H*W-1) { if(l==r) { sgt[p]={{X[l],X[l]},{Y[l],Y[l]}}; return; } int mid=(l+r)/2; if(id<=mid) update(id,p*2,l,mid); else update(id,p*2+1,mid+1,r); sgt[p].x.x=min(sgt[p*2].x.x, sgt[p*2+1].x.x); sgt[p].y.x=min(sgt[p*2].y.x, sgt[p*2+1].y.x); sgt[p].x.y=max(sgt[p*2].x.y, sgt[p*2+1].x.y); sgt[p].y.y=max(sgt[p*2].y.y, sgt[p*2+1].y.y); } pair<pair<int,int>,pair<int,int>> get(int a, int b, int p=1, int l=0, int r=H*W-1) { if(l==r) return sgt[p]; int mid=(l+r)/2; // l mid a b int mnX=1e9, mxX=-1, mnY=1e9, mxY=-1; if(l<=b && mid>=a) { auto pr=get(a,b,p*2,l,mid); mnX=min(mnX,pr.x.x); mxX=max(mxX,pr.x.y); mnY=min(mnY,pr.y.x); mxY=max(mxY,pr.y.y); } if(mid+1<=b && r>=a) { auto pr=get(a,b,p*2+1,mid+1,r); mnX=min(mnX,pr.x.x); mxX=max(mxX,pr.x.y); mnY=min(mnY,pr.y.x); mxY=max(mxY,pr.y.y); } return {{mnX,mxX},{mnY,mxY}}; } void give_initial_chart(int h,int w, vector<int> y, vector<int> x) { H=h, W=w; X=x, Y=y; sgt.resize(4*H*W); build(); } int swap_seats(int a, int b) { swap(X[a],X[b]); swap(Y[a],Y[b]); update(a), update(b); int ret=0; int ptr=0; while(ptr<H*W) { auto gt=get(0,ptr); int where=(gt.x.y-gt.x.x+1)*(gt.y.y-gt.y.x+1)-1; if(where==ptr) { ret++; ptr++; } else ptr=where; } return ret; }
#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...