Submission #299738

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

seats

#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];

int calcXmin(int l,int r){
	int a=H;
	l+=(1<<20);
	r+=(1<<20);
	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<<20);
	r+=(1<<20);
	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<<20);
	r+=(1<<20);
	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<<20);
	r+=(1<<20);
	while(l<=r){
		a=max({a,treeYmax[l],treeYmax[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

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