| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 256885 |
2020-08-03T10:57:07 Z |
doowey |
Tram (CEOI13_tram) |
C++14 |
|
316 ms |
19052 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)2e5 + 10;
const ll inf = (ll)1e14;
set<pii> pos;
set<int> rows;
set<pair<ll,pii>> shit;
bool has[N][2];
int n;
vector<pii> cells(int l, int r){
vector<pii> res;
for(int i = 0 ; i < 2; i ++ ){
if(!has[l][i]){
res.push_back(mp(l, i));
}
if(!has[l+1][i]){
res.push_back(mp(l+1,i));
}
}
for(int i = 0 ; i < 2; i ++ ){
if(r > l + 1){
if(!has[r][i]){
res.push_back(mp(r, i));
}
if(r - 1 > l + 1){
if(!has[r - 1][i]){
res.push_back(mp(r-1,i));
}
}
}
}
if((r - l - 1) >= 3){
int mid = (l + r) / 2;
for(int q = 0; q < 2; q ++ ){
res.push_back(mp(mid,q));
if((r - l - 1) % 2 == 0)
res.push_back(mp(mid + 1, q));
}
}
return res;
}
ll Q(ll d){
return d * d;
}
ll compute(int x, int y){
ll ans = inf;
auto it = pos.lower_bound(mp(x,y));
auto pv = it;
for(int q = 0; q < 2; q ++ ){
if(it != pos.end()){
ans = min(ans, Q(it->fi - x) + Q(it->se - y));
it ++ ;
}
}
for(int q = 0; q < 2 ; q ++ ){
if(pv != pos.begin()) pv -- ;
if(pv != pos.end()){
ans = min(ans, Q(pv->fi - x) + Q(pv->se - y));
}
}
return ans;
}
void add(int x, int y){
auto it = rows.upper_bound(x);
auto pv = it;
pv -- ;
vector<pii> shi = cells(*pv, *it);
for(auto f : shi)
shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
auto qq = pv;
if(qq != rows.begin()){
qq -- ;
if(*pv == x){
shi = cells(*qq, *pv);
for(auto f : shi)
shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
}
}
has[x][y]=true;
pos.insert(mp(x,y));
rows.insert(x);
it = rows.lower_bound(x);
pv = it;
pv -- ;
shi = cells(*pv, *it);
for(auto f : shi)
shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
pv = it;
pv ++ ;
shi = cells(*it, *pv);
for(auto f : shi)
shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
}
void delet(int x, int y){
auto it = rows.lower_bound(x);
auto pv = it;
pv --;
vector<pii> shi = cells(*pv, *it);
for(auto f : shi)
shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
pv = it;
pv ++ ;
shi = cells(*it, *pv);
for(auto f : shi)
shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
pos.erase(mp(x,y));
has[x][y]=false;
if(!has[x][0] && !has[x][1]){
rows.erase(x);
it = rows.lower_bound(x);
pv = it;
pv -- ;
shi = cells(*pv, *it);
for(auto f : shi)
shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
}
else{
it = rows.lower_bound(x);
pv = it;
pv -- ;
shi = cells(*pv, *it);
for(auto f : shi)
shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
pv = it;
pv ++ ;
shi = cells(*it, *pv);
for(auto f : shi)
shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
}
}
pii id[N];
int main(){
fastIO;
int q;
cin >> n >> q;
rows.insert(0);
rows.insert(n+1);
for(int q = 0; q < 2; q ++ ){
has[0][q]=true;
has[n+1][q]=true;
}
vector<pii> shi = cells(0, n + 1);
for(auto f : shi)
shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
char typ;
pii cur;
int tyi;
ll dis;
for(int t = 0; t < q; t ++ ){
cin >> typ;
if(typ == 'E'){
auto fx = shit.end();
-- fx;
if(fx->fi == inf){
id[t] = mp(1,0);
add(1,0);
cout << 1 << " " << 1 << "\n";
}
else{
dis = fx->fi;
fx = shit.lower_bound(mp(dis,mp(-1,-1)));
id[t] = mp(fx->se.fi, fx->se.se);
cout << fx->se.fi << " " << fx->se.se + 1 << "\n";
add(fx->se.fi, fx->se.se);
}
}
else{
cin >> tyi;
tyi--;
delet(id[tyi].fi, id[tyi].se);
}
}
return 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 |
| # |
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 |
7 ms |
620 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Correct |
9 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
620 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Correct |
9 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Correct |
9 ms |
876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
3180 KB |
Output is correct |
| 2 |
Correct |
90 ms |
876 KB |
Output is correct |
| 3 |
Correct |
161 ms |
3052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
19052 KB |
Output is correct |
| 2 |
Correct |
128 ms |
876 KB |
Output is correct |
| 3 |
Correct |
251 ms |
6124 KB |
Output is correct |
