Submission #328932

#	Time	Username	Problem	Language	Result	Execution time	Memory
328932		tzxydby	Tram (CEOI13_tram)	C++11	100 / 100	119 ms	9324 KiB

tram

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m,a[N][3],x[N],y[N];
inline long long dis(long long x1,long long y1,long long x2,long long y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
struct node
{
	int l,r,px,py;
	long long d;
	void upd()
	{
		if(l==0)
		{
			if(a[r][1]&&a[r][2])
				px=1,py=1,d=dis(px,py,r,1);
			else if(a[r][1])
				px=1,py=2,d=dis(px,py,r,1);
			else if(a[r][2])
				px=1,py=1,d=dis(px,py,r,2);
			return;
		}
		if(r==n+1)
		{
			if(a[l][1]&&a[l][2])
				px=n,py=1,d=dis(px,py,l,1);
			else if(a[l][1])
				px=n,py=2,d=dis(px,py,l,1);
			else if(a[l][2])
				px=n,py=1,d=dis(px,py,l,2);
			return;
		}
		int x[5],y[5],c=0;
		if(a[l][1])x[c]=l,y[c]=1,c++;
		if(a[l][2])x[c]=l,y[c]=2,c++;
		if(a[r][1])x[c]=r,y[c]=1,c++;
		if(a[r][2])x[c]=r,y[c]=2,c++;
		d=0;
		for(int rx=(l+r)/2-1;rx<=(l+r)/2+1;rx++)
		{
			for(int ry=1;ry<=2;ry++)
			{
				if(rx<l||rx>r)
					continue;
				long long w=1e18;
				for(int i=0;i<c;i++)
					w=min(w,dis(rx,ry,x[i],y[i]));
				if(w>d)
					d=w,px=rx,py=ry;
			}
		}
	}
	bool operator<(const node k)const
	{
		return d==k.d?px<k.px:d>k.d;
	}
}b[N];
set<int>s;
set<node>t;
void add(int p,int c)
{
	a[p][c]=1;
	if(a[p][3-c]==1)
	{
		auto it=s.lower_bound(p);
		int pre=*(--it);
		t.erase(b[pre]);
		t.erase(b[p]);
		b[pre].upd();
		b[p].upd();
		t.insert(b[pre]);
		t.insert(b[p]);
	}
	else
	{
		auto it=s.lower_bound(p);
		int suf=*it,pre=*(--it);
		t.erase(b[pre]);
		b[pre].r=p;
		b[p].l=p,b[p].r=suf;
		b[pre].upd();
		b[p].upd();
		t.insert(b[pre]);
		t.insert(b[p]);
		s.insert(p);
	}
}
void del(int p,int c)
{
	a[p][c]=0;
	if(a[p][3-c]==1)
	{
		auto it=s.lower_bound(p);
		int pre=*(--it);
		t.erase(b[pre]);
		t.erase(b[p]);
		b[pre].upd();
		b[p].upd();
		t.insert(b[pre]);
		t.insert(b[p]);
	}
	else
	{
		s.erase(p);
		auto it=s.lower_bound(p);
		int suf=*it,pre=*(--it);
		t.erase(b[pre]);
		t.erase(b[p]);
		b[pre].r=suf;
		b[pre].upd();
		t.insert(b[pre]);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	s.insert(0);
	s.insert(n+1);
	b[0].l=0,b[0].r=n+1;
	b[0].upd();
	t.insert(b[0]);
	for(int i=1;i<=m;i++)
	{
		char op;
		cin>>op;
		if(op=='E')
		{
			int px,py;
			if(s.size()==2)
				px=1,py=1;
			else
				px=t.begin()->px,py=t.begin()->py;
			x[i]=px,y[i]=py;
			add(px,py);
			cout<<px<<' '<<py<<endl;
		}
		else
		{
			int r;
			cin>>r;
			del(x[r],y[r]);
		}
	}
	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