oj.uz

Submission #39690

# Submission time Handle Problem Language Result Execution time Memory
39690 2018-01-17T10:17:42 Z aome Tram (CEOI13_tram) C++14
100 / 100
 112 ms 4588 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
 
const int N = 150005;
 
typedef pair<int, int> ii;
typedef pair<long long, ii> II;
typedef set<int> :: iterator it;
 
int n, m;
int mask[N];
ii res[N];
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(-1LL * (y - 1) * (y - 1), ii(1, 1));
		else return II(-1LL * (y - 1) * (y - 1) - 1, ii(1, 3 ^ my)); 
	}
	if (!y) {
		if (mx == 3) return II(-1LL * (n - x) * (n - x), ii(n, 1));
		else return II(-1LL * (n - x) * (n - x) - 1, ii(n, 3 ^ mx));
	}
	int mid = (x + y) / 2;
	if (mx == 3 && my == 3) {
		return II(-1LL * (mid - x) * (mid - x), ii(mid, 1));
	}
	else if (mx == 3) {
		mid = (x + y + 1) / 2;
		if (x % 2 != y % 2) return II(-1LL * (y - mid) * (y - mid) - 1, ii(mid, 3 ^ my));
		else return II(-1LL * (mid - x) * (mid - x), ii(mid, 1));
	}
	else if (my == 3) {
		if (x % 2 != y % 2) return II(-1LL * (mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
		else return II(-1LL * (y - mid) * (y - mid), ii(mid, 1));
	}
	else {
		if (mx == my) {
			return II(-1LL * (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(-1LL * (mid - x) * (mid - x), ii(mid, 1));
			}
			else {
				return II(-1LL * (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);
	if (tmp.fi) s2.insert(tmp);
	s.erase(x);
}
 
int main() {
	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:59:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   59 |  if (i == --s.end()) return 0; return *(++i);
      |  ^~
tram.cpp:59:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   59 |  if (i == --s.end()) return 0; return *(++i);
      |                                ^~~~~~
tram.cpp: In function 'int prv(it)':
tram.cpp:63:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   63 |  if (i == s.begin()) return 0; return *(--i);
      |  ^~
tram.cpp:63:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |  if (i == s.begin()) return 0; return *(--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 7 ms 492 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1132 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 5 ms 1004 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1132 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 6 ms 1004 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 2412 KB Output is correct
2 Correct 81 ms 748 KB Output is correct
3 Correct 76 ms 1692 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4588 KB Output is correct
2 Correct 110 ms 876 KB Output is correct
3 Correct 78 ms 2284 KB Output is correct