| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 39689 |
2018-01-17T10:14:00 Z |
aome |
Tram (CEOI13_tram) |
C++14 |
|
137 ms |
4716 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<int, 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(-(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;
if (x % 2 != y % 2) return II(-(y - mid) * (y - mid) - 1, ii(mid, 3 ^ my));
else return II(-(mid - x) * (mid - x), ii(mid, 1));
}
else if (my == 3) {
if (x % 2 != y % 2) return II(-(mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
else return II(-(y - mid) * (y - mid), ii(mid, 1));
}
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);
if (tmp.fi) 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: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);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
492 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
4 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
492 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
4 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
1004 KB |
Output isn't correct |
| # |
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 |
Incorrect |
5 ms |
1004 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
2540 KB |
Output is correct |
| 2 |
Correct |
99 ms |
748 KB |
Output is correct |
| 3 |
Correct |
105 ms |
1816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
4716 KB |
Output is correct |
| 2 |
Correct |
67 ms |
876 KB |
Output is correct |
| 3 |
Runtime error |
8 ms |
1644 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
