oj.uz

Submission #53085

# Submission time Handle Problem Language Result Execution time Memory
53085 2018-06-28T08:54:33 Z 0^0(#1394) Tram (CEOI13_tram) C++11
10 / 100
 38 ms 8288 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));
				}
			}
		}
	}
	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);
	if (!cnt[p[idx].first]) {
		l[p[idx].first][p[idx].second ^ 3] = 1;
		pq.push({ 1,{-p[idx].first,-(p[idx].second ^ 3)} });
	}
	l[p[idx].first][p[idx].second] = inf;
	trip[p[idx].first][p[idx].second] = 1;
	cnt[p[idx].first]++;
	auto it = line.lower_bound(p[idx].first);
	auto le = it;
	auto ri = it;
	--le;
	++ri;
	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;
	l[x][1] = l[x][2] = inf;
}
void erase(int idx) {
	trip[p[idx].first][p[idx].second] = 0;
	if (!--cnt[p[idx].first]) {
		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 3 ms 3968 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4076 KB Output is correct
2 Incorrect 3 ms 3948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4076 KB Output is correct
2 Incorrect 4 ms 3948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5476 KB Output is correct
2 Incorrect 21 ms 4460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8288 KB Output is correct
2 Incorrect 21 ms 4436 KB Output isn't correct
3 Halted 0 ms 0 KB -