Submission #75110

#	Time	Username	Problem	Language	Result	Execution time	Memory
75110		Namnamseo	Seats (IOI18_seats)	C++17	100 / 100	2454 ms	56848 KiB

seats

#include <bits/stdc++.h>
using namespace std;

int n, h, w;
int z;

const int M = 1048576;
int tree[M<<1];
int lazy[M<<1];
int cmn[M<<1];

int iv[int(1e6)+10];

inline void pd(int p){
	if(!lazy[p]) return;
	for(int c=p*2; c<=p*2+1; ++c){
		tree[c] += lazy[p];
		lazy[c] += lazy[p];
	}
	lazy[p]=0;
}

inline void gather(int p){
	if(tree[p*2] == tree[p*2+1]){
		tree[p] = tree[p*2];
		cmn[p] = cmn[p*2]+cmn[p*2+1];
	} else if(tree[p*2] > tree[p*2+1]){
		tree[p] = tree[p*2+1];
		cmn[p] = cmn[p*2+1];
	} else {
		tree[p] = tree[p*2];
		cmn[p] = cmn[p*2];
	}
}

void init(int p=1, int l=1, int r=n){
	if(l==r){
		tree[p]=iv[l];
		cmn[p]=1;
		return;
	}
	int mid=(l+r)/2;
	init(p*2, l, mid);
	init(p*2+1, mid+1, r);
	gather(p);
}

void upd(int l, int r, int v, int mp=1, int ml=1, int mr=n){
	if(r<ml || mr<l) return;
	if(ml!=mr) pd(mp);
	if(l<=ml && mr<=r){
		tree[mp] += v;
		lazy[mp] += v;
		return;
	}
	int mid=(ml+mr)/2;
	upd(l,r,v, mp*2, ml, mid);
	upd(l,r,v, mp*2+1, mid+1, mr);
	gather(mp);
}

inline void addr(int x, int y){
	if(x>=y) return;
	upd(x, y-1, 1);
}

inline void delr(int x, int y){
	if(x>=y) return;
	upd(x, y-1, -1);
}

int Arr[3*int(1e6)+10];

int arr[4];
inline void add(int x, int y){
	arr[0]=Arr[x*z+y]; if(!arr[0]) arr[0]=1e9;
	arr[1]=Arr[x*z+y+1]; if(!arr[1]) arr[1]=1e9;
	arr[2]=Arr[(x+1)*z+y]; if(!arr[2]) arr[2]=1e9;
	arr[3]=Arr[(x+1)*z+y+1]; if(!arr[3]) arr[3]=1e9;
	sort(arr, arr+4);
	addr(arr[0], arr[1]);
	addr(arr[2], arr[3]);
}

inline void del(int x, int y){
	arr[0]=Arr[x*z+y]; if(!arr[0]) arr[0]=1e9;
	arr[1]=Arr[x*z+y+1]; if(!arr[1]) arr[1]=1e9;
	arr[2]=Arr[(x+1)*z+y]; if(!arr[2]) arr[2]=1e9;
	arr[3]=Arr[(x+1)*z+y+1]; if(!arr[3]) arr[3]=1e9;
	sort(arr, arr+4);
	delr(arr[0], arr[1]);
	delr(arr[2], arr[3]);
}

int mx[int(1e6)+1];
int my[int(1e6)+1];

inline void addr2(int x, int y){
	if(x>=y) return;
	y = min(y, n+1);
	iv[x]+=1;
	iv[y]-=1;
}

inline void add2(int x, int y){
	arr[0]=Arr[x*z+y]; if(!arr[0]) arr[0]=1e9;
	arr[1]=Arr[x*z+y+1]; if(!arr[1]) arr[1]=1e9;
	arr[2]=Arr[(x+1)*z+y]; if(!arr[2]) arr[2]=1e9;
	arr[3]=Arr[(x+1)*z+y+1]; if(!arr[3]) arr[3]=1e9;
	sort(arr, arr+4);
	addr2(arr[0], arr[1]);
	addr2(arr[2], arr[3]);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	h=H; w=W; n=h*w;
	z=w+2;
	for(int i=1; i<=n; ++i){
		int x=R[i-1]+1, y=C[i-1]+1;
		mx[i]=x; my[i]=y;
		Arr[x*z+y] = i;
	}

	for(int i=0; i<=h; ++i){
		for(int j=0; j<=w; ++j){
			add2(i, j);
		}
	}

	for(int i=1; i<=n; ++i) iv[i]+=iv[i-1];

	init();
}

#define rep(i,n) for(int i=0; i<(n); ++i)

int swap_seats(int A, int B) {
	++A; ++B;
	int ax=mx[A], ay=my[A];
	rep(dx,2) rep(dy,2) del(ax-dx, ay-dy);
	Arr[ax*z+ay]=B;
	rep(dx,2) rep(dy,2) add(ax-dx, ay-dy);

	int bx=mx[B], by=my[B];
	rep(dx,2) rep(dy,2) del(bx-dx, by-dy);
	Arr[bx*z+by]=A;
	rep(dx,2) rep(dy,2) add(bx-dx, by-dy);

	mx[A]=bx; my[A]=by;
	mx[B]=ax; my[B]=ay;
	return (tree[1]==4) ? (cmn[1]) : 0;
}

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