Submission #39686

# Submission time Handle Problem Language Result Execution time Memory
39686 2018-01-17T09:49:38 Z aome Tram (CEOI13_tram) C++14
0 / 100
106 ms 4572 KB
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 150005;
const int M = 30005;

typedef pair<int, int> ii;
typedef pair<int, ii> II;
typedef set<int> :: iterator it;

int n, m;
int mask[N];
ii res[M];
set<int> s;
multiset<II> s2; 

II cal(int x, int y) {
	int mx = mask[x], my = mask[y];
	if (!x && !y) return II(0, ii(0, 0));
	if (!x) {
		if (my == 3) return II(-(y - 1) * (y - 1), ii(1, 1));
		else return II(-(y - 1) * (y - 1) - 1, ii(1, 3 ^ my)); 
	}
	if (!y) {
		if (mx == 3) return II(-(n - x) * (n - x), ii(n, 1));
		else return II(-(n - x) * (n - x) - 1, ii(n, 3 ^ mx));
	}
	int mid = (x + y) / 2;
	if (mx == 3 && my == 3) {
		return II(-(mid - x) * (mid - x), ii(mid, 1));
	}
	else if (mx == 3) {
		mid = (x + y + 1) / 2;
		return II(-(y - mid) * (y - mid) - 1, ii(mid, 3 ^ my));
	}
	else if (my == 3) {
		return II(-(mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
	}
	else {
		if (mx == my) {
			return II(-(mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
		}
		else {
			if (x % 2 == y % 2) {
				if (x + 2 == y) return II(-1, ii(mid - 1, 3 ^ mx));
				return II(-(mid - x) * (mid - x), ii(mid, 1));
			}
			else {
				return II(-(mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
			}
		}
	}
}

int nxt(it i) {
	if (i == --s.end()) return 0; return *(++i);
}

int prv(it i) {
	if (i == s.begin()) return 0; return *(--i);
}

void add(int x) {
	it i = s.lower_bound(x);
	int l, r;
	l = prv(i);
	if (i == s.end()) r = 0; else r = *i;

	II tmp = cal(l, r);	
	if (tmp.fi) s2.erase(s2.find(tmp));
	tmp = cal(l, x), s2.insert(tmp);
	tmp = cal(x, r), s2.insert(tmp);
	s.insert(x);
}

void rem(int x) {
	it i = s.lower_bound(x);
	int l, r;
	l = prv(i), r = nxt(i);
	II tmp;
	tmp = cal(l, x), s2.erase(s2.find(tmp));
	tmp = cal(x, r), s2.erase(s2.find(tmp));
	tmp = cal(l, r), s2.insert(tmp);
	s.erase(x);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		char type; cin >> type;
		if (type == 'E') {
			if (!s2.size()) {
				res[i] = ii(1, 1), mask[1] |= 1, add(1);
			}
			else {
				II tmp = *s2.begin();
				res[i] = tmp.se; 
				if (mask[res[i].fi]) {
					rem(res[i].fi), mask[res[i].fi] |= 1 << (res[i].se - 1), add(res[i].fi);
				}
				else {
					mask[res[i].fi] |= 1 << (res[i].se - 1), add(res[i].fi);
				}
			}
			cout << res[i].fi << ' ' << res[i].se << '\n';
		}
		else {
			int pos; cin >> pos;
			rem(res[pos].fi), mask[res[pos].fi] ^= (1 << (res[pos].se - 1));
			if (mask[res[pos].fi]) add(res[pos].fi);
		}
	}
}

Compilation message

tram.cpp: In function 'int nxt(it)':
tram.cpp:58:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   58 |  if (i == --s.end()) return 0; return *(++i);
      |  ^~
tram.cpp:58:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   58 |  if (i == --s.end()) return 0; return *(++i);
      |                                ^~~~~~
tram.cpp: In function 'int prv(it)':
tram.cpp:62:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   62 |  if (i == s.begin()) return 0; return *(--i);
      |  ^~
tram.cpp:62:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   62 |  if (i == s.begin()) return 0; return *(--i);
      |                                ^~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 1132 KB Output is correct
2 Incorrect 5 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 1132 KB Output is correct
2 Runtime error 4 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 2488 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 106 ms 4572 KB Output is correct
2 Runtime error 2 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -