#include<stdio.h>
#include<algorithm>
#include<set>
#define Set_itr set<int>::iterator
#define SetA_itr set<A>::iterator
using namespace std;
set<int>Set;
Set_itr be, ed;
int n, m, dat[31000];
struct A{
int d, r, a, b;
bool operator <(const A &p)const{
return d != p.d ? d < p.d : r > p.r;
}
}tp;
set<A>Set2;
int dist(int a, int b){
int x = a / 2, y = b / 2, r;
if (x < y)r = y - x;
else r = x - y;
r *= 2;
if (a % 2 != b % 2) r++;
if (r == 1)r = 2;
return r;
}
void Print(int a){
printf("%d %d\n", a / 2 + 1, a % 2 + 1);
}
A Sol(Set_itr it){
A res;
Set_itr it2 = it,it3=it,it4;
int y, my, i, t, R = -1, dis, rr;
it2++; it4 = it2;
if (it3 != be)it3--;
if (it4 != ed)it4++;
res.a = *it, res.b = *it2;
y = (res.a / 2 + res.b / 2)/2;
my = y;
if ((res.a / 2 + res.b / 2) & 1)my++;
if (res.b / 2 - res.a / 2 == 2){
y--, my++;
}
while (y <= my){
for (i = 0; i < 2; i++){
t = y * 2 + i;
if (t<res.a || t>res.b)continue;
dis = min(min(dist(t, *it), dist(t, *it2)), min(dist(t, *it3), dist(t, *it4)));
if (R < dis)R = dis, rr = t;
}
y++;
}
res.d = R, res.r = rr;
return res;
}
void Ins(Set_itr it){
if (it != ed){
tp = Sol(it);
Set2.insert(tp);
it++;
if (it != ed){
tp = Sol(it);
Set2.insert(tp);
}
it--;
}
if (it != be){
it--;
Set2.insert(Sol(it));
if (it != be){
it--;
tp = Sol(it);
Set2.insert(tp);
it++;
}
}
}
void Pro(Set_itr it){
if (it != Set.begin() && it != Set.end()){
it--;
Set2.erase(Set2.find(Sol(it)));
}
}
void Put(int cnt, int t){
dat[cnt] = t;
Print(t);
Set_itr it=Set.lower_bound(t),it2;
Pro(it);
if (it != Set.begin()){
it2 = it; it2--;
Pro(it2);
}
if (it != Set.end()){
it2 = it; it2++;
Pro(it2);
}
Set.insert(t);
be = Set.begin();
ed = Set.end();
ed--;
Ins(Set.find(t));
}
void insert(int cnt){
int sz = Set.size(), t, d, r;
Set_itr it = be, it2;
t = 1 - (*it % 2);
if (sz > 1){
it2 = it; it2++;
if (*it2 / 2 == *it / 2)t = 0;
}
d = dist(t, *it), r = t;
it = ed;
t = n * 2 - 1 - (*it % 2);
if (sz > 1){
it2 = it; it2--;
if (*it2 / 2 == *it / 2)t = n * 2 - 2, it = it2;
}
if (d < dist(t, *it))d = dist(t, *it), r = t;
if (Set2.empty()){
Put(cnt, r);
return;
}
SetA_itr iit;
if (!Set2.empty()){
iit = Set2.end(); iit--;
if (iit->d > d || (d == iit->d &&iit->r < r))d = iit->d, r = iit->r;
}
Put(cnt, r);
return;
}
void del(Set_itr it){
if (it != ed){
Set2.erase(Set2.find(Sol(it)));
it++;
if (it != ed)Set2.erase(Set2.find(Sol(it)));
it--;
}
if (it != be){
it--;
Set2.erase(Set2.find(Sol(it)));
if (it != be){
it--;
Set2.erase(Set2.find(Sol(it)));
it++;
}
it++;
}
int t = *it;
Set.erase(it);
if (Set.empty())return;
be = Set.begin();
ed = Set.end(); ed--;
Set_itr it2 = Set.lower_bound(t);
if (it2 != be && it2 != Set.end()){
it2--;
Set2.insert(Sol(it2));
it2++;
}
if (it2 != be){
it2--;
if (it2 != be){
it2--;
Set2.insert(Sol(it2));
it2++;
}
it2++;
}
if (it2 != ed && it2!=Set.end()){
Set2.insert(Sol(it2));
}
}
int main(){
scanf("%d%d", &n, &m);
char pp[2];
int cnt = 0, a;
while (m--){
scanf("%s", pp);
cnt++;
if (!Set.empty()){
be = Set.begin();
ed = Set.end();
ed--;
}
else{
Put(cnt, 0);
continue;
}
if (pp[0] == 'E'){
insert(cnt);
}
else{
scanf("%d", &a);
del(Set.find(dat[a]));
}
}
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
172 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
176 | scanf("%s", pp);
| ~~~~~^~~~~~~~~~
tram.cpp:191:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
191 | scanf("%d", &a);
| ~~~~~^~~~~~~~~~
tram.cpp: In function 'A Sol(std::set<int>::iterator)':
tram.cpp:53:9: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
53 | return res;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
496 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
480 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
492 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
83 ms |
3888 KB |
Output is correct |
| 2 |
Correct |
83 ms |
876 KB |
Output is correct |
| 3 |
Correct |
69 ms |
1640 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
78 ms |
3948 KB |
Output is correct |
| 2 |
Correct |
74 ms |
876 KB |
Output is correct |
| 3 |
Correct |
74 ms |
1776 KB |
Output is correct |
