/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
if (res > val) { res = val; return true; } return false; }
typedef pair<ll,ll> ii;
typedef pair<ll,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 30300;
struct node
{
ll dis , x , y , l , r;
node(){}
node(int dis , int x , int y , int l , int r): dis(dis), x(x), y(y), l(l), r(r) {}
bool operator < (const node k) const
{
if (dis == k.dis) return C(x,y) > C(k.x,k.y);
return dis < k.dis;
}
};
set <int> p;
set <ii> t;
int f[200100][2];
map <ii,ii> k;
vector <node> xl;
int n , m;
iii max2(iii x , iii y)
{
if (x.fi == y.fi)
{
if (x.se < y.se) return x;
return y;
}
return max(x,y);
}
iii find(int x , int y)
{
if (x == 0 && y == n + 1) return C(n*n + 1,C(1,0));
if (x == 0)
{
if (!f[y][0]) return C((y - 1)*(y - 1) + 1,C(1,0));
if (!f[y][1]) return C((y - 1)*(y - 1) + 1,C(1,1));
if (!f[1][0])
return C((y - 1)*(y - 1),C(1,0));
else return C((y - 1)*(y - 1),C(1,1));
}
if (y == n + 1)
{
if (!f[x][0]) return C((n - x)*(n - x) + 1,C(n,0));
if (!f[x][1]) return C((n - x)*(n - x) + 1,C(n,1));
if (!f[n][0])
return C((n - x)*(n - x),C(n,0));
else return C((n - x)*(n - x),C(n,1));
}
ll k = (x + y);
ll z = k/2;
iii res = C(0,C(0,0));
if (!f[z][0]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][0] == 0),C(z,0ll)),C(1ll*(y - z)*(y - z) + (f[y][0] == 0),C(z,0ll))));
if (!f[z][1]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][1] == 0),C(z,1ll)),C(1ll*(y - z)*(y - z) + (f[y][1] == 0),C(z,1ll))));
z = k/2 + 1;
if (z <= y)
{
if (!f[z][0]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][0] == 0),C(z,0ll)),C(1ll*(y - z)*(y - z) + (f[y][0] == 0),C(z,0ll))));
if (!f[z][1]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][1] == 0),C(z,1ll)),C(1ll*(y - z)*(y - z) + (f[y][1] == 0),C(z,1ll))));
}
z = k/2 - 1;
if (z >= x)
{
if (!f[z][0]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][0] == 0),C(z,0ll)),C(1ll*(y - z)*(y - z) + (f[y][0] == 0),C(z,0ll))));
if (!f[z][1]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][1] == 0),C(z,1ll)),C(1ll*(y - z)*(y - z) + (f[y][1] == 0),C(z,1ll))));
}
return res;
}
set <ii> a;
set <node> b;
set <node> T[150100];
ii T2[N];
ii per[N];
void input()
{
cin >> n >> m;
}
void solve()
{
a.insert(C(0,0));
a.insert(C(n + 1,0));
b.insert(node(n,1,0,0,n + 1));
p.insert(0);
p.insert(n + 1);
int cnt = 0;
while (m--)
{
cnt++;
char v;
cin >> v;
if (v == 'E')
{
auto d = b.end();
d--;
int x = (*d).x;
int y = (*d).y;
f[x][y] = 1;
a.insert(C(x,y));
per[cnt] = C(x,y);
cout << x << " " << y + 1 << "\n";
p.erase(x);
auto l = p.lower_bound(x);
auto r = l;
l--;
iii X = find(*l,x);
iii Y = find(x,*r);
b.insert(node(X.fi,X.two,X.thr,(*d).l,x));
b.insert(node(Y.fi,Y.two,Y.thr,x,(*d).r));
T[(*d).l].insert(node(X.fi,X.two,X.thr,(*d).l,x));
T[(*d).x].insert(node(X.fi,X.two,X.thr,(*d).l,x));
T[(*d).x].insert(node(Y.fi,Y.two,Y.thr,x,(*d).r));
T[(*d).r].insert(node(Y.fi,Y.two,Y.thr,x,(*d).r));
b.erase(d);
p.insert(x);
}
else
{
int x;
cin >> x;
int A = per[x].fi;
int B = per[x].se;
a.erase(per[x]);
if (!(f[per[x].fi][per[x].se]^1)) p.erase(per[x].fi);
auto l = a.lower_bound(per[x]);
auto r = l;
l--;
for (node v : T[A])
{
b.erase(v);
if (v.l == A && v.r == A) xl.push_back(v);
else
{
if (v.l == A) T[v.r].erase(v);
else T[v.l].erase(v);
}
}
// cout << (*l).fi << " - " << (*r).fi << "\n";
T[A].clear();
f[per[x].fi][per[x].se] = 0;
iii K = find((*l).first,(*r).first);
b.insert(node(K.fi,K.two,K.thr,(*l).first,(*r).first));
T[(*l).first].insert(node(K.fi,K.two,K.thr,(*l).first,(*r).first));
T[(*r).first].insert(node(K.fi,K.two,K.thr,(*l).first,(*r).first));
}
}
}
void solve2()
{
a.insert(C(0,0));
a.insert(C(n + 1,0));
int cnt = 0;
while (m--)
{
cnt++;
char v;
cin >> v;
if (v == 'E')
{
iii res = C(0,C(0,0));
for (auto d = a.begin() ; d != a.end() ; d++)
{
auto k = ++d;
d--;
if (k == a.end()) break;
// if (cnt == 6) cout << (*d).fi << " " <<(*d).se << "\n";
// cout << (*d).fi << " " << (*k).fi << "\n";
res = max2(res,find((*d).fi,(*k).fi));
}
f[res.two][res.thr] = 1;
// cout << find(1,4).fi;
cout << res.two << " " << res.thr + 1 << "\n";
T2[cnt] = C(res.two,res.thr);
a.insert(C(res.two,res.thr));
}
else
{
int x;
cin >> x;
int X = T2[x].fi;
int Y = T2[x].se;
a.erase(C(X,Y));
f[X][Y] = 0;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
if(fopen(TASK".inp", "r")){
freopen(TASK".inp","r",stdin);
freopen(TASK".out","w",stdout);
}
int tk;
tk = 1;
//cin >> tk;
while (tk--)
{
input();
if (n >= 15000 && m >= 30000)
solve();else solve2();
}
return 0;
}
Compilation message
tram.cpp: In function 'void solve()':
tram.cpp:175:17: warning: unused variable 'B' [-Wunused-variable]
175 | int B = per[x].se;
| ^
tram.cpp: In function 'int main()':
tram.cpp:262:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
262 | freopen(TASK".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tram.cpp:263:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
263 | freopen(TASK".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
80 ms |
7520 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7396 KB |
Output is correct |
| 3 |
Correct |
24 ms |
7452 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
77 ms |
7456 KB |
Output is correct |
| 2 |
Correct |
11 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
30 ms |
7452 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
126 ms |
8612 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7396 KB |
Output is correct |
| 3 |
Correct |
29 ms |
8612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
123 ms |
8612 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7380 KB |
Output is correct |
| 3 |
Incorrect |
31 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
17484 KB |
Output is correct |
| 2 |
Correct |
740 ms |
8152 KB |
Output is correct |
| 3 |
Correct |
67 ms |
12108 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
23860 KB |
Output is correct |
| 2 |
Correct |
607 ms |
8216 KB |
Output is correct |
| 3 |
Incorrect |
47 ms |
12904 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
