Submission #274851

#	Time	Username	Problem	Language	Result	Execution time	Memory
274851		arnold518	Tram (CEOI13_tram)	C++14	0 / 100	127 ms	9580 KiB

tram

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const int MAXM = 3e4;

int N, Q, A[MAXN+10];
pii ans[MAXN+10];
map<int, int> M;

struct Point
{
	ll d; int x, y; int l, r;
	Point() : d(-1), l(-1), r(-1) {}
	Point(ll d, int x, int y, int l, int r) : d(d), x(x), y(y), l(l), r(r) {}
	bool operator < (const Point &p) const
	{
		if(d==p.d)
		{
			if(x==p.x)
			{
				if(y==p.y)
				{
					if(l==p.l) return r<p.r;
					return l<p.l;
				}
				return y<p.y;
			}
			return x<p.x;
		}
		return d>p.d;
	}
};

multiset<Point> S;

ll dist(ll x1, ll y1, ll x2, ll y2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

vector<Point> get(int l, int r)
{
	vector<Point> V;
	{
		int x1=l, x2=r;
		int y1=M[l], y2=M[r];
		int nx, ny;
		if(y1==3) y1=1; if(y2==3) y2=1;

		nx=(x1+x2)/2, ny=1;
		ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
		V.push_back(Point(now, nx, ny, l, r));

		nx=(x1+x2)/2+1, ny=1;
		now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
		V.push_back(Point(now, nx, ny, l, r));
	}

	{
		int x1=l, x2=r;
		int y1=M[l], y2=M[r];
		int nx, ny;
		if(y1==3) y1=2; if(y2==3) y2=2;

		nx=(x1+x2)/2, ny=2;
		ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
		V.push_back(Point(now, nx, ny, l, r));

		nx=(x1+x2)/2+1, ny=2;
		now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
		V.push_back(Point(now, nx, ny, l, r));
	}

	return V;
}

void push(Point p)
{
	vector<Point> V;
	if(p.l!=-1 && p.r!=-1)
	{
		V=get(p.l, p.r);
		for(auto it : V) S.erase(it);
	}
	M[p.x]+=p.y;
	auto it=M.find(p.x);
	if(it!=M.begin())
	{
		V=get(prev(it)->first, it->first);
		for(auto it : V) S.insert(it);
	}
	if(next(it)!=M.end())
	{
		V=get(it->first, next(it)->first);
		for(auto it : V) S.insert(it);
	}
}

void pop(int x, int y)
{
	vector<Point> V;
	auto it=M.find(x);
	if(it!=M.begin())
	{
		V=get(prev(it)->first, it->first);
		for(auto it : V) S.erase(it);
	}
	if(next(it)!=M.end())
	{
		V=get(it->first, next(it)->first);
		for(auto it : V) S.erase(it);
	}
	M[x]-=y;
	if(M[x]!=0)
	{
		auto it=M.find(x);
		if(it!=M.begin())
		{
			V=get(prev(it)->first, it->first);
			for(auto it : V) S.insert(it);
		}
		if(next(it)!=M.end())
		{
			V=get(it->first, next(it)->first);
			for(auto it : V) S.insert(it);
		}
	}
	else
	{
		M.erase(x);
		auto it=M.lower_bound(x);
		if(it==M.end() || it==M.begin()) return;
		V=get(prev(it)->first, it->first);
		for(auto it : V) S.insert(it);
	}
}

int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=Q; i++)
	{
		char c;
		scanf(" %c", &c);
		if(c=='E') A[i]=-1;
		else scanf("%d", &A[i]);
	}

	for(int i=1; i<=Q; i++)
	{
		if(A[i]==-1)
		{
			Point p;
			if(M.empty())
			{
				ans[i]={1, 1};
				p.x=1; p.y=1;
				push(p);
				printf("%d %d\n", 1, 1);
				continue;
			}

			if(!S.empty()) p=*S.begin();

			{
				int x1=M.begin()->first, y1=M.begin()->second;
				if(y1==3) y1=1;
				int nx=1, ny=1;
				ll now=dist(nx, ny, x1, y1);
				p=min(p, Point(now, nx, ny, -1, -1));
			}
			{
				int x1=M.begin()->first, y1=M.begin()->second;
				if(y1==3) y1=2;
				int nx=1, ny=2;
				ll now=dist(nx, ny, x1, y1);
				p=min(p, Point(now, nx, ny, -1, -1));
			}
			{
				int x1=(--M.end())->first, y1=(--M.end())->second;
				if(y1==3) y1=1;
				int nx=N, ny=1;
				ll now=dist(nx, ny, x1, y1);
				p=min(p, Point(now, nx, ny, -1, -1));
			}
			{
				int x1=(--M.end())->first, y1=(--M.end())->second;
				if(y1==3) y1=2;
				int nx=N, ny=2;
				ll now=dist(nx, ny, x1, y1);
				p=min(p, Point(now, nx, ny, -1, -1));
			}

			ans[i]={p.x, p.y};
			push(p);
			printf("%d %d\n", p.x, p.y);
		}
		else
		{
			int x=ans[A[i]].first, y=ans[A[i]].second;
			pop(x, y);
		}
	}
}

Compilation message (stderr)

tram.cpp: In function 'std::vector<Point> get(int, int)':
tram.cpp:53:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   53 |   if(y1==3) y1=1; if(y2==3) y2=1;
      |   ^~
tram.cpp:53:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   53 |   if(y1==3) y1=1; if(y2==3) y2=1;
      |                   ^~
tram.cpp:68:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |   if(y1==3) y1=2; if(y2==3) y2=2;
      |   ^~
tram.cpp:68:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |   if(y1==3) y1=2; if(y2==3) y2=2;
      |                   ^~
tram.cpp: In function 'int main()':
tram.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  145 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~
tram.cpp:151:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  151 |   else scanf("%d", &A[i]);
      |        ~~~~~^~~~~~~~~~~~~

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