Submission #400587

#	Time	Username	Problem	Language	Result	Execution time	Memory
400587		mosiashvililuka	Seats (IOI18_seats)	C++17	100 / 100	2385 ms	115364 KiB

seats

#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[4000009],seg2[4000009],n,l,r,z,zz,za,jm[4000009];
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[6];
	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 update2(int q, int w, int rr){
	int X[6];
	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){
		jm[l]+=z;
		jm[r+1]-=z;
	}
	l=X[3];r=X[4]-1;z=rr*6;
	if(l<=r){
		jm[l]+=z;
		jm[r+1]-=z;
	}
}
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++){
			update2(i,j,1);
		}
	}
	for(i=1; i<=za; i++){
		jm[i]+=jm[i-1];
		seg[za+i-1]=1;
		segmn[za+i-1]=jm[i];
	}
	for(int rr=za-1; rr>=1; rr--){
		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 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;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30