Submission #328891

#	Time	Username	Problem	Language	Result	Execution time	Memory
328891		htc001	Tram (CEOI13_tram)	C++14	100 / 100	98 ms	12780 KiB

tram

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

int readint(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}

int ntmp;
int ctmp[15];

void printint(int x){
	ntmp=0;
	while(x){
		ctmp[++ntmp]=x%10;
		x/=10;
	}
	while(ntmp) putchar(ctmp[ntmp--]+'0');
}

typedef pair<int,int> pii;
typedef pair<long long,pii> plii;
typedef pair<int,pii> piii;
const int N=150005;
int n,q,m,cs;
int used[N][2],lft[N];
pii ap[N];
set<int> st,one;
set<piii> bt[3][3];

inline int Status(int x){
	if(used[x][0]==1&&used[x][1]==1) return 2;
	if(used[x][0]) return 0;
	if(used[x][1]) return 1;
	return -1;
}

void iinsert(int x,int y){
	if(Status(x)!=Status(y)) bt[Status(x)][Status(y)].insert(make_pair(x-y,make_pair(x,y)));
	else bt[Status(x)][Status(y)].insert(make_pair(-((y-x)/2),make_pair(x,y)));
}

void eerase(int x,int y){
	if(Status(x)!=Status(y)) bt[Status(x)][Status(y)].erase(make_pair(x-y,make_pair(x,y)));
	else bt[Status(x)][Status(y)].erase(make_pair(-((y-x)/2),make_pair(x,y)));
}

void Dec(int x){
	int pre=-1,suf=-1;
	set<int>::iterator it=st.find(x);
	if(it!=st.begin()){
		it--;
		pre=*it;
		it++;
	}
	it++;
	if(it!=st.end()) suf=*it;
	it--;
	if(pre!=-1) eerase(pre,x);
	if(suf!=-1) eerase(x,suf);
	if(pre!=-1&&suf!=-1) iinsert(pre,suf);
	st.erase(x);
}

void Inc(int x){
	st.insert(x);
	int pre=-1,suf=-1;
	set<int>::iterator it=st.find(x);
	if(it!=st.begin()){
		it--;
		pre=*it;
		it++;
	}
	it++;
	if(it!=st.end()) suf=*it;
	it--;
	if(pre!=-1) iinsert(pre,x);
	if(suf!=-1) iinsert(x,suf);
	if(pre!=-1&&suf!=-1) eerase(pre,suf);
}

void Insert(int x,int y){
	if(Status(x)!=-1) Dec(x);
	m++;
	used[x][y]=1;
	lft[x]--;
	if(!lft[x]) one.erase(x);
	ap[cs]=make_pair(x,y);
	printint(x);
	putchar(' ');
	printint(y+1);
	putchar('\n');
	Inc(x);
}

void Erase(int x,int y){
	Dec(x);
	m--;
	used[x][y]=0;
	if(!lft[x]) one.insert(x);
	lft[x]++;
	if(Status(x)!=-1) Inc(x);
}

plii MAX(plii x,plii y){
	if(x.first>y.first) return x;
	if(x.first<y.first) return y;
	if(x.second<y.second) return x;
	return y;
}

int main(){
	n=readint();
	q=readint();
	for(int i=1;i<=n;i++){
		lft[i]=2;
		one.insert(i);
	}
	while(++cs<=q){
		char ch=getchar();
		while(ch!='E'&&ch!='L') ch=getchar();
		if(ch=='E'){
			if(m==0) Insert(1,0);
			else{
				plii ans=make_pair(0ll,pii(0,0));
				for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(!bt[i][j].empty()){
					int x=bt[i][j].begin()->second.first,y=bt[i][j].begin()->second.second;
					int mid=(x+y)/2;
					for(int ii=mid;ii<=min(mid+1,y);ii++) for(int jj=0;jj<2;jj++) if(!used[ii][jj]){
						long long dis=1000000000000000000ll;
						for(int k=0;k<2;k++){
							if(used[x][k]) dis=min(dis,1ll*(x-ii)*(x-ii)+1ll*(k-jj)*(k-jj));
							if(used[y][k]) dis=min(dis,1ll*(y-ii)*(y-ii)+1ll*(k-jj)*(k-jj));
						}
						ans=MAX(ans,make_pair(dis,pii(ii,jj)));
					}
				}
				set<int>::iterator it=st.begin();
				int x=*it;
				int ii=1;
				for(int jj=0;jj<2;jj++) if(!used[ii][jj]){
					long long dis=1000000000000000000ll;
					for(int k=0;k<2;k++) if(used[x][k]) dis=min(dis,1ll*(x-ii)*(x-ii)+1ll*(k-jj)*(k-jj));
					ans=MAX(ans,make_pair(dis,pii(ii,jj)));
				}
				it=st.end();it--;x=*it;
				ii=n;
				for(int jj=0;jj<2;jj++) if(!used[ii][jj]){
					long long dis=1000000000000000000ll;
					for(int k=0;k<2;k++) if(used[x][k]) dis=min(dis,1ll*(x-ii)*(x-ii)+1ll*(k-jj)*(k-jj));
					ans=MAX(ans,make_pair(dis,pii(ii,jj)));
				}
				if(ans.first==1ll){
					int x=*one.begin();
					ans.second.first=x;
					if(!used[x][0]) ans.second.second=0;
					else ans.second.second=1;
				}
				Insert(ans.second.first,ans.second.second);
			}
		}else{
			int qr,x,y;
			qr=readint();
			x=ap[qr].first;y=ap[qr].second;
			Erase(x,y);
		}
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20