Submission #299712

#	Time	Username	Problem	Language	Result	Execution time	Memory
299712		TMJN	Seats (IOI18_seats)	C++17	5 / 100	4029 ms	56976 KiB

seats

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

int H,W;
vector<pair<int,int>>XY;
int treeXmin[1<<19],treeXmax[1<<19],treeYmin[1<<19],treeYmax[1<<19];

int calcXmin(int l,int r){
	int a=H;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=min({a,treeXmin[l],treeXmin[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}
int calcXmax(int l,int r){
	int a=0;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=max({a,treeXmax[l],treeXmax[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}
int calcYmin(int l,int r){
	int a=W;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=min({a,treeYmin[l],treeYmin[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}
int calcYmax(int l,int r){
	int a=0;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=max({a,treeYmax[l],treeYmax[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

int next_Xmin(int t){
	int m=calcXmin(0,t);
	int k=t+(1<<18);
	while(m<=treeXmin[k]&&k!=1){
		k=(k+1)/2;
	}
	while(k<(1<<18)){
		if(treeXmin[k+k]<m){
			k=k+k;
		}
		else{
			k=k+k+1;
		}
	}
	return k-(1<<18);
}
int next_Xmax(int t){
	int m=calcXmax(0,t);
	int k=t+(1<<18);
	while(m>=treeXmax[k]&&k!=1){
		k=(k+1)/2;
	}
	while(k<(1<<18)){
		if(treeXmax[k+k]>m){
			k=k+k;
		}
		else{
			k=k+k+1;
		}
	}
	return k-(1<<18);	
}
int next_Ymin(int t){	
	int m=calcYmin(0,t);
	int k=t+(1<<18);
	while(m<=treeYmin[k]&&k!=1){
		k=(k+1)/2;
	}
	while(k<(1<<18)){
		if(treeYmin[k+k]<m){
			k=k+k;
		}
		else{
			k=k+k+1;
		}
	}
	return k-(1<<18);
}
int next_Ymax(int t){
	int m=calcYmax(0,t);
	int k=t+(1<<18);
	while(m>=treeYmax[k]&&k!=1){
		k=(k+1)/2;
	}
	while(k<(1<<18)){
		if(treeYmax[k+k]>m){
			k=k+k;
		}
		else{
			k=k+k+1;
		}
	}
	return k-(1<<18);
}

void update(int x){
	int t=x;
	x+=(1<<18);
	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.push_back({R[i],C[i]});
	}
	for(int i=0;i<H*W;i++){
		treeXmin[i+(1<<18)]=treeXmax[i+(1<<18)]=XY[i].first;
		treeYmin[i+(1<<18)]=treeYmax[i+(1<<18)]=XY[i].second;
	}
	treeXmin[H*W+(1<<18)]=treeYmin[H*W+(1<<18)]=-0xE869120;
	treeXmax[H*W+(1<<18)]=treeYmax[H*W+(1<<18)]=0xE869120;
	for(int i=(1<<18)-1;i;i--){
		treeXmin[i]=min(treeXmin[i+i],treeXmin[i+i+1]);
		treeXmax[i]=max(treeXmax[i+i],treeXmax[i+i+1]);
		treeYmin[i]=min(treeYmin[i+i],treeYmin[i+i+1]);
		treeYmax[i]=max(treeYmax[i+i],treeYmax[i+i+1]);
	}
}

int swap_seats(int a,int b){
	if(a>b)swap(a,b);
	swap(XY[a],XY[b]);
	update(a);
	update(b);
	int res=0;
	int t=0;
	while(t<H*W){
		if((calcXmax(0,t)-calcXmin(0,t)+1)*(calcYmax(0,t)-calcYmin(0,t)+1)==t+1){
			res++;
		}
		t=max(t+1,min({next_Xmin(t),next_Xmax(t),next_Ymin(t),next_Ymax(t)})-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