| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 400571 | mosiashvililuka | 자리 배치 (IOI18_seats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,seg[4000009],segmn[400009],seg2[4000009],n,l,r,z,zz,za;
pair <int, int> p[1000009];
vector <vector <int> > f;
void pushdown(int q, int w, int rr){
if(q!=w){
seg2[rr*2]+=seg2[rr];
seg2[rr*2+1]+=seg2[rr];
}
segmn[rr]+=seg2[rr];
seg2[rr]=0;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]=z;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
if(segmn[rr*2]<segmn[rr*2+1]){
seg[rr]=seg[rr*2];
segmn[rr]=segmn[rr*2];
}
if(segmn[rr*2+1]<segmn[rr*2]){
seg[rr]=seg[rr*2+1];
segmn[rr]=segmn[rr*2+1];
}
if(segmn[rr*2]==segmn[rr*2+1]){
seg[rr]=seg[rr*2]+seg[rr*2+1];
segmn[rr]=segmn[rr*2];
}
}
void read(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
if(z>segmn[rr]){
zz=seg[rr];
z=segmn[rr];
}else{
if(z==segmn[rr]){
zz+=seg[rr];
}
}
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void update(int q, int w, int rr){
int X[9];
X[1]=f[q][w];
X[2]=f[q+1][w];
X[3]=f[q][w+1];
X[4]=f[q+1][w+1];
sort(X+1,X+5);
l=X[1];r=X[2]-1;z=rr;
if(l<=r) upd(1,za,1);
l=X[3];r=X[4]-1;z=rr*6;
if(l<=r) upd(1,za,1);
}
void bld(int q, int w, int rr){
segmn[rr]=0;seg[rr]=w-q+1;
if(q==w) return;
bld(q,(q+w)/2,rr*2);
bld((q+w)/2+1,w,rr*2+1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
a=H;b=W;
n=a*b;
f.resize(H+6);
za=1;
while(za<n+6) za*=2;
bld(1,za,1);
for(i=0; i<=H+4; i++){
f[i].resize(W+6);
}
for(i=1; i<=H*W; i++){
R[i-1]++;C[i-1]++;
p[i].first=R[i-1];
p[i].second=C[i-1];
f[R[i-1]][C[i-1]]=i;
}
for(i=0; i<=H+1; i++){
f[i][0]=f[i][W+1]=n+4;
}
for(i=0; i<=W+1; i++){
f[0][i]=f[H+1][i]=n+4;
}
for(i=0; i<=H; i++){
for(j=0; j<=W; j++){
update(i,j,1);
}
}
}
void UPD(int q, int w, int rr){
update(q-1,w-1,rr);
update(q-1,w,rr);
update(q,w-1,rr);
update(q,w,rr);
}
int swap_seats(int C, int D) {
C++;D++;
c=C;d=D;
UPD(p[c].first,p[c].second,-1);
f[p[c].first][p[c].second]=d;
UPD(p[c].first,p[c].second,1);
UPD(p[d].first,p[d].second,-1);
f[p[d].first][p[d].second]=c;
UPD(p[d].first,p[d].second,1);
swap(p[c],p[d]);
z=n+2;zz=0;
l=1;r=n;
read(1,za,1);
if(z!=4){
return 0;
}else{
return zz;
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
vector <int> qw,we;
cin>>a>>b;
for(i=1; i<=a*b; i++){
cin>>c;
qw.push_back(c);
}
for(i=1; i<=a*b; i++){
cin>>c;
we.push_back(c);
}
give_initial_chart(a,b,qw,we);
l=1;r=n;z=n+2;zz=0;
read(1,za,1);
while(1){
cin>>c>>d;
cout<<swap_seats(c,d)<<endl;
}
return 0;
}