Submission #299769

#	Time	Username	Problem	Language	Result	Execution time	Memory
299769		TMJN	Seats (IOI18_seats)	C++17	5 / 100	4035 ms	56056 KiB

seats

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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];

inline int calcXmin(int l,int r){
	int a=H;
	l+=(1<<20);
	r+=(1<<20);
	while(l<=r){
		if(a<treeXmin[l]&&a<treeXmin[r]){
		}
		else if(treeXmin[l]<treeXmin[r]){
			a=treeXmin[l];
		}
		else{
			a=treeXmin[r];
		}
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}
inline int calcXmax(int l,int r){
	int a=0;
	l+=(1<<20);
	r+=(1<<20);
	while(l<=r){
		if(a>treeXmax[l]&&a>treeXmax[r]){
		}
		else if(treeXmax[l]>treeXmax[r]){
			a=treeXmax[l];
		}
		else{
			a=treeXmax[r];
		}
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}
inline int calcYmin(int l,int r){
	int a=W;
	l+=(1<<20);
	r+=(1<<20);
	while(l<=r){
		if(a<treeYmin[l]&&a<treeYmin[r]){
		}
		else if(treeYmin[l]<treeYmin[r]){
			a=treeYmin[l];
		}
		else{
			a=treeYmin[r];
		}
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}
inline int calcYmax(int l,int r){
	int a=0;
	l+=(1<<20);
	r+=(1<<20);
	while(l<=r){
		if(a>treeYmax[l]&&a>treeYmax[r]){
		}
		else if(treeYmax[l]>treeYmax[r]){
			a=treeYmax[l];
		}
		else{
			a=treeYmax[r];
		}
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

inline 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);
}

inline 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--){
		if(treeXmin[i+i]<treeXmin[i+i+1]){
			treeXmin[i]=treeXmin[i+i];
		}
		else{
			treeXmin[i]=treeXmin[i+i+1];
		}
		if(treeXmax[i+i]>treeXmax[i+i+1]){
			treeXmax[i]=treeXmax[i+i];
		}
		else{
			treeXmax[i]=treeXmax[i+i+1];
		}
		
		if(treeYmin[i+i]<treeYmin[i+i+1]){
			treeYmin[i]=treeYmin[i+i];
		}
		else{
			treeYmin[i]=treeYmin[i+i+1];
		}
		if(treeYmax[i+i]>treeYmax[i+i+1]){
			treeYmax[i]=treeYmax[i+i];
		}
		else{
			treeYmax[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;
}

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