oj.uz

Submission #274847

# Submission time Handle Problem Language Result Execution time Memory
274847 2020-08-19T17:13:27 Z arnold518 Tram (CEOI13_tram) C++14
90 / 100
 131 ms 9580 KB 
#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) 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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 748 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 5 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 748 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 6 ms 492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 748 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 5 ms 492 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4192 KB Output is correct
2 Correct 131 ms 1004 KB Output is correct
3 Correct 101 ms 3180 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 9580 KB Output is correct
2 Correct 103 ms 1004 KB Output is correct
3 Correct 121 ms 3436 KB Output is correct