| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53314 |
2018-06-29T09:07:42 Z |
Petr(#1976) |
Tram (CEOI13_tram) |
C++11 |
|
69 ms |
7980 KB |
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pp=pair<int,int>;
#define x first
#define y second
#define DBG if(0)
multiset<int> filled_row;
int n;
bool m[150010][2];
pp history[30010];
set<pair<ll, pp>> candidate;
int get_bef(int x){
auto it = filled_row.lower_bound(x);
if(it == filled_row.begin()) return 0;
else return *--it;
}
int get_nxt(int x){
auto it = filled_row.upper_bound(x);
if(it == filled_row.end()) return n+1;
else return *it;
}
ll hypo(ll dx, ll dy){ return dx*dx + !!dy; }
inline void add_range(int d, int u){
if(d+1 >= u) return;
pair<ll, pp> ans[2]; int an = 0;
auto eval = [&](int r, int c){
ll Md = 1ll << 60;
for(int br = d; br <= u; br += u-d){
for(int bc = 0; bc < 2; ++bc){
if(m[br][bc]) Md = min(Md, hypo(r - br, c - bc));
}
}
if(an == 0 || -ans[0].x == Md) ans[an++] = make_pair(-Md, pp(r, c));
else if(-ans[0].x < Md){
ans[0] = make_pair(-Md, pp(r, c));
an = 1;
}
};
if(d == 0){
if(u == n+1){
candidate.emplace(0, pp(1, 0));
return;
} else {
eval(1, 0); eval(1, 1);
}
} else if(u == n+1){
eval(n, 0); eval(n, 1);
} else for(int r = (d+u)/2; r <= (d+u+1)/2; ++r){
for(int c = 0; c < 2; ++c){
eval(r, c);
}
}
for(int i=0; i<an; ++i) candidate.emplace(ans[i]);
}
inline void remove_range(int d, int u){
if(d+1 >= u) return;
pair<ll, pp> ans[2]; int an = 0;
auto eval = [&](int r, int c){
ll Md = 1ll << 60;
for(int br = d; br <= u; br += u-d){
for(int bc = 0; bc < 2; ++bc){
if(m[br][bc]) Md = min(Md, hypo(r - br, c - bc));
}
}
if(an == 0 || -ans[0].x == Md) ans[an++] = make_pair(-Md, pp(r, c));
else if(-ans[0].x < Md){
ans[0] = make_pair(-Md, pp(r, c));
an = 1;
}
};
if(d == 0){
if(u == n+1){
candidate.erase(make_pair(0, pp(1, 0)));
return;
} else {
eval(1, 0); eval(1, 1);
}
} else if(u == n+1){
eval(n, 0); eval(n, 1);
} else for(int r = (d+u)/2; r <= (d+u+1)/2; ++r){
for(int c = 0; c < 2; ++c){
eval(r, c);
}
}
for(int i=0; i<an; ++i) candidate.erase(ans[i]);
}
int main()
{
int q;
scanf("%d%d", &n, &q);
add_range(0, n+1);
for(int i=1; i<=q; ++i){
char com[5];
scanf("%s", com);
if(com[0] == 'E'){
assert(candidate.size());
auto tmp = *candidate.begin();
int px, py; tie(px, py) = candidate.begin() -> second;
printf("%d %d\n", px, py+1);
history[i] = {px, py};
int bef = get_bef(px), nxt = get_nxt(px);
filled_row.insert(px);
if(m[px][py^1]){
remove_range(bef, px); remove_range(px, nxt);
m[px][py] = 1;
add_range(bef, px); add_range(px, nxt);
} else {
remove_range(bef, nxt);
m[px][py] = 1;
add_range(bef, px); add_range(px, nxt);
candidate.emplace(-1, pp(px, py^1));
}
candidate.erase(tmp);
} else {
int idx, x, y;
scanf("%d", &idx);
tie(x, y) = history[idx];
assert(filled_row.find(x) != filled_row.end());
filled_row.erase(filled_row.find(x));
int bef = get_bef(x), nxt = get_nxt(x);
remove_range(bef, x);
remove_range(x, nxt);
m[x][y] = 0;
if(m[x][y^1]){
add_range(bef, x);
add_range(x, nxt);
candidate.emplace(-1, pp(x, y));
} else {
add_range(bef, nxt);
candidate.erase(make_pair(-1, pp(x, y^1)));
}
}
DBG printf("Candidates no.: %d\n", int(candidate.size()));
DBG for(auto tmp:candidate){
printf("Dist^2 = %lld. pt %2d %2d\n", -tmp.x, tmp.y.x, tmp.y.y);
}
}
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
105 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
110 | scanf("%s", com);
| ~~~~~^~~~~~~~~~~
tram.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
135 | scanf("%d", &idx);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
492 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
492 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1012 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1004 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
2540 KB |
Output is correct |
| 2 |
Runtime error |
5 ms |
876 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
7980 KB |
Output is correct |
| 2 |
Runtime error |
5 ms |
876 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
