oj.uz

Submission #53128

# Submission time Handle Problem Language Result Execution time Memory
53128 2018-06-28T13:54:05 Z baactree Tram (CEOI13_tram) C++17
100 / 100
 51 ms 10680 KB 
#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.0 / 10.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3948 KB Output is correct
2 Correct 3 ms 3820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4076 KB Output is correct
2 Correct 3 ms 3948 KB Output is correct
3 Correct 4 ms 4076 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4076 KB Output is correct
2 Correct 3 ms 3948 KB Output is correct
3 Correct 5 ms 4076 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5100 KB Output is correct
2 Correct 4 ms 3948 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 3948 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5568 KB Output is correct
2 Correct 23 ms 4460 KB Output is correct
3 Correct 33 ms 5612 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10680 KB Output is correct
2 Correct 22 ms 4460 KB Output is correct
3 Correct 51 ms 6564 KB Output is correct