oj.uz

Submission #328914

# Submission time Handle Problem Language Result Execution time Memory
328914 2020-11-18T13:01:11 Z tzxydby Tram (CEOI13_tram) C++11
0 / 100
 77 ms 748 KB 
#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;
		}
		if(a[l][1]&&a[l][2])
		{
			if(a[r][1]&&a[r][2])
				px=(l+r)/2,py=1,d=dis(px,py,l,1);
			else if(a[r][1])
				px=(l+r+1)/2,py=2,d=dis(px,py,r,1);
			else if(a[r][2])
				px=(l+r+1)/2,py=1,d=dis(px,py,r,2);
		}
		else if(a[l][1])
			px=(l+r)/2,py=2,d=dis(px,py,l,1);
		else if(a[l][2])
			px=(l+r)/2,py=1,d=dis(px,py,l,2);
	}
	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][c^1]==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 pre=*(--it),suf=*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][c^1]==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 pre=*(--it),suf=*it;
		t.erase(b[pre]);
		t.erase(b[p]);
		b[pre].r=suf;
		b[pre].upd();
		t.insert(b[p]);
		s.erase(p);
	}
}
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -