Submission #53128

#	Time	Username	Problem	Language	Result	Execution time	Memory
53128		baactree	Tram (CEOI13_tram)	C++17	100 / 100	51 ms	10680 KiB

tram

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
set<int> line;
bool trip[150005][3];
ll l[150005][3];
int cnt[150005];
pair<int, int> p[30005];
priority_queue<pair<ll, pair<int, int> > > pq;
const ll inf = 0x3f3f3f3f3f3f3f3f;
pair<int, int> get_p() {
	while (!pq.empty() && l[-pq.top().second.first][-pq.top().second.second] != pq.top().first)pq.pop();
	if (pq.empty())return { 1,1 };
	pair<int, int> ret = { -pq.top().second.first,-pq.top().second.second };
	pq.pop();
	return ret;
}
ll dist(ll x1, ll y1, ll x2, ll y2) {
	ll x = x2 - x1;
	ll y = y2 - y1;
	return x * x + y * y;
}
void update(int le, int ri) {
	if ((le==0&&ri==n+1)||ri - le <= 1)return;
	int x = 0;
	if (le == 0) {
		x = 1;
		l[x][1] = l[x][2] = inf;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= 2; j++) {
				if (trip[ri][j]) {
					l[x][i] = min(l[x][i],dist(x, i, ri, j));
				}
			}
		}
	}
	else if (ri == n + 1) {
		x = n;
		l[x][1] = l[x][2] = inf;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= 2; j++) {
				if (trip[le][j]) {
					l[x][i] = min(l[x][i], dist(x, i, le, j));
				}
			}
		}
	}
	else {
		x = (le + ri) / 2;
		l[x][1] = l[x][2] = inf;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= 2; j++) {
				if (trip[ri][j]) {
					l[x][i] = min(l[x][i], dist(x, i, ri, j));
				}
			}
		}
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= 2; j++) {
				if (trip[le][j]) {
					l[x][i] = min(l[x][i], dist(x, i, le, j));
				}
			}
		}
		if ((ri - le) & 1) {
			pq.push({ l[x][1],{ -x,-1 } });
			pq.push({ l[x][2],{ -x,-2 } });
			x++;
			l[x][1] = l[x][2] = inf;
			for (int i = 1; i <= 2; i++) {
				for (int j = 1; j <= 2; j++) {
					if (trip[ri][j]) {
						l[x][i] = min(l[x][i], dist(x, i, ri, j));
					}
				}
			}
			for (int i = 1; i <= 2; i++) {
				for (int j = 1; j <= 2; j++) {
					if (trip[le][j]) {
						l[x][i] = min(l[x][i], dist(x, i, le, j));
					}
				}
			}
		}
	}
	pq.push({ l[x][1],{-x,-1} });
	pq.push({ l[x][2],{-x,-2} });
}
void insert(int idx) {
	p[idx] = get_p();
	cout << p[idx].first << " " << p[idx].second << '\n';
	line.insert(p[idx].first);
	auto it = line.lower_bound(p[idx].first);
	auto le = it;
	auto ri = it;
	--le;
	++ri;
	for (int i = max(*le + 1, *it - 1); i <= min(*ri - 1, *it + 1); i++)
		l[i][1] = l[i][2] = inf;
	if (!cnt[p[idx].first]) {
		l[p[idx].first][p[idx].second ^ 3] = 1;
		pq.push({ 1,{-p[idx].first,-(p[idx].second ^ 3)} });
	} 
	trip[p[idx].first][p[idx].second] = 1;
	cnt[p[idx].first]++;
	update(*le, *it);
	update(*it, *ri);
}
void dupdate(int le, int ri) {
	if (ri - le <= 1)return;
	int x = 0;
	if (le == 0)x = 1;
	else if (ri == n + 1)x = n;
	else {
		x = (le + ri) / 2;
		if ((ri - le) & 1) {
			l[x][1] = l[x][2] = inf;
			x++;
		}
	}
	l[x][1] = l[x][2] = inf;
}
void erase(int idx) {
	trip[p[idx].first][p[idx].second] = 0;
	if (!--cnt[p[idx].first]) {
		l[p[idx].first][p[idx].second ^ 3] = inf;
		auto it = line.lower_bound(p[idx].first);
		auto le = it;
		auto ri = it;
		--le; 
		++ri;
		dupdate(*le, *it);
		dupdate(*it, *ri);
		update(*le, *ri);
		line.erase(it);
	}
	else {
		auto it = line.lower_bound(p[idx].first);
		auto le = it;
		auto ri = it;
		--le;
		++ri;
		update(*le, *it);
		update(*it, *ri);
		l[p[idx].first][p[idx].second] = 1;
		pq.push({ 1,{-p[idx].first,-p[idx].second} });
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(l, 0x3f, sizeof(l));
	cin >> n >> m;
	line.insert(0);
	line.insert(n + 1);
	for (int i = 1; i <= m; i++) {
		char t;
		cin >> t;
		if (t == 'E') {
			insert(i);
		}
		else {
			int x;
			cin >> x;
			erase(x);
		}
	}
	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