#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 1e6+6,inf = 1e8;
int F[N],ANS[N];
vector<pii> Q[N];
void qer(int v,int tl,int tr,int l,int r,int QL,int QR) {
if (l > tr || r < tl) return;
if (l <= tl && r >= tr) {
Q[v].pb({QL,QR});
return;
}
int tm = (tl + tr)/2;
qer(v*2,tl,tm,l,r,QL,QR);
qer(v*2+1,tm+1,tr,l,r,QL,QR);
}
int L[2][10000000],R[2][1000000],A[2][1000000],id[2]={1,1};
int PX,PY,C[2][1000000];
// x >= PX, y-minimal
int get_y(int vy,int tl,int tr) {
if (!vy || !A[vy]) return inf;
if (tl == tr) {
if (A[0][vy]) return tl;
return inf;
}
int tm = (tl + tr)/2;
int a = get_y(L[0][vy],tl,tm);
if (a != inf) return a;
return get_y(R[0][vy],tm+1,tr);
// return max( get_y(L[vy],tl,tm), get_y(R[vy]))
}
int get_x(int vx,int tlx,int trx) {
if (trx < PX || !vx) return inf;
if (tlx >= PX) {
if (C[0][vx])
return get_y(C[0][vx],1,1e6);
else return inf;
}
int tmx = (tlx + trx)/2;
int a = inf,b = inf;
if (L[0][vx]) a = get_x(L[0][vx],tlx,tmx);
if (R[0][vx]) b = get_x(R[0][vx],tmx+1,trx);
return min(a,b);
}
void upd_y(int vy,bool flag,int tl,int tr,int val,int a,int b) {
// if (tr < PY || tl > PY) return;
if (tl == tr) {
if (flag)
A[0][vy]+=val;
else A[0][vy] = A[0][a] + A[0][b];
return;
}
else {
int tm = (tl + tr)/2;
if (tl <= tm) {
if (!L[0][vy]) L[0][vy] = ++id[0];
upd_y(L[0][vy],flag,tl,tm,val,L[0][a],L[0][b]);
}else {
if (!R[0][vy]) R[0][vy] = ++id[0];
upd_y(R[0][vy],flag,tm+1,tr,val,R[0][a],R[0][b]);
}
}
A[0][vy] = A[0][L[0][vy]] + A[0][R[0][vy]];
}
void upd_x(int vx,int tlx,int trx,int val) {
// if (PX > trx || PX < tlx) return;
if (tlx < trx) {
int tmx = (tlx + trx)/2;
if (PX <= tmx) {
if (!L[0][vx]) L[0][vx] = ++id[0];
upd_x(L[0][vx],tlx,tmx,val);
}else {
if (!R[0][vx]) R[0][vx] = ++id[0];
upd_x(R[0][vx],tmx+1,trx,val);
}
}
if (!C[0][vx]) C[0][vx] = ++id[0];
upd_y(C[0][vx],tlx == trx,1,1e6,val,C[0][L[0][vx]],C[0][R[0][vx]]);
}
// x <= PX, y max
int GET_Y(int vy,int tl,int tr) {
if (!vy || !A[vy]) return -inf;
if (tl == tr) {
if (A[1][vy]) return tl;
return -inf;
}
int tm = (tl + tr)/2;
int a = GET_Y(R[1][vy],tm+1,tr);
if (a != -inf) return a;
return GET_Y(L[1][vy],tl,tm);
// return max( get_y(L[vy],tl,tm), get_y(R[vy]))
}
int GET_X(int vx,int tlx,int trx) {
if (tlx > PX || !vx) return -inf;
if (trx <= PX) {
if (C[1][vx])
return GET_Y(C[1][vx],1,1e6);
else return -inf;
}
int tmx = (tlx + trx)/2;
int a = -inf,b = -inf;
if (L[1][vx]) a = GET_X(L[1][vx],tlx,tmx);
if (R[1][vx]) b = GET_X(R[1][vx],tmx+1,trx);
return max(a,b);
}
void UPD_Y(int vy,bool flag,int tl,int tr,int val,int a,int b) {
// if (tr < PY || tl > PY) return;
if (tl == tr) {
if (flag)
A[1][vy]+=val;
else A[1][vy] = A[1][a] + A[1][b];
return;
}
else {
int tm = (tl + tr)/2;
if (tl <= tm) {
if (!L[1][vy]) L[1][vy] = ++id[1];
UPD_Y(L[1][vy],flag,tl,tm,val,L[1][a],L[1][b]);
}else {
if (!R[1][vy]) R[1][vy] = ++id[1];
UPD_Y(R[1][vy],flag,tm+1,tr,val,R[1][a],R[1][b]);
}
}
A[1][vy] = A[1][L[1][vy]] + A[1][R[1][vy]];
}
void UPD_X(int vx,int tlx,int trx,int val) {
//cout <<"OG";
// if (PX > trx || PX < tlx) return;
if (tlx < trx) {
int tmx = (tlx + trx)/2;
if (PX <= tmx) {
if (!L[1][vx]) L[1][vx] = ++id[1];
UPD_X(L[1][vx],tlx,tmx,val);
}else {
if (!R[1][vx]) R[1][vx] = ++id[1];
UPD_X(R[1][vx],tmx+1,trx,val);
}
}
if (!C[1][vx]) C[1][vx] = ++id[1];
UPD_Y(C[1][vx],tlx == trx,1,1e6,val,C[1][L[1][vx]],C[1][R[1][vx]]);
}
int cans=INT_MAX;
int t[2][4*N],timer;
int *H[100000000];
int val[10000000];
void change(int&x,int c) {
++timer;
H[timer] = &x;
val[timer] = x;
x = c;
}
void rollback() {
(*H[timer]) = val[timer];
timer--;
}
void add(int v,int tl,int tr,int pos,int val,int type) {
if (tl == tr) {
if (type == 0)
change(t[0][v],min(t[0][v],val));
else change(t[1][v],max(t[1][v],val));
// t[0][v] += val;
return;
}
int tm = (tl + tr)/2;
if (pos <= tm) {
add(v*2,tl,tm,pos,val,type);
}
else add(v*2+1,tm+1,tr,pos,val,type);
if (type == 0)
change(t[0][v],min(t[0][v*2],t[0][v*2+1]));
else
change(t[1][v],max(t[1][v*2],t[1][v*2+1]));
//t[v] = t[v*2] + t[v*2+1];
}
int get(int v,int tl,int tr,int l,int r,int type) {
if (l > tr || r < tl) {
if (type == 0) return inf;
else return -inf;
}
if (l <= tl && r >= tr) return t[type][v];
int tm = (tl + tr)/2;
if (type == 0)
return min(get(v*2,tl,tm,l,r,type),get(v*2+1,tm+1,tr,l,r,type));
else return max(get(v*2,tl,tm,l,r,type),get(v*2+1,tm+1,tr,l,r,type));
}
void dfs(int v,int tl,int tr) {
int in_ans = cans;
int start_time = timer;
for (auto i1 : Q[v]) {
int l = i1.fi;
int r = i1.se;
PX = r;
// PY = r;
cans = min(cans, -l + get(1,1,1e6,r,1e6,0));
PX = l;
cans = min(cans, r - get(1,1,1e6,1,l,1));
PX = l;
PY = r;
add(1,1,1e6,l,r,0); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
add(1,1,1e6,r,l,1);
PX = r;
PY = l;
// UPD_X(1,1,1e6,1);
}
if (tl != tr) {
int tm = (tl + tr)/2;
dfs(v*2,tl,tm);
dfs(v*2+1,tm+1,tr);
}else {
if (F[tl])
ANS[tl] = cans;//,cout << cans <<'s'<<'\n';
}
while(start_time != timer) {
rollback();
}/*
for (auto i1 : Q[v]) {
int l = i1.fi;
int r = i1.se;
// PX = r;
// PY = r;
// cans = min(cans, -l + get_x(1,1,1e6);
// PX = l;
// cans = min(cans, r - GET_X(1,1,1e6));
PX = l;
PY = r;
upd_x(1,1,1e6,-1); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
PX = r;
PY = l;
UPD_X(1,1,1e6,-1);
}*/
cans = in_ans;
}
main() {
int q;
cin >> q;
multiset<int> L,R;
multiset<int> AL[1004],AR[1004];
map<pii,vector<int> > cnt;
for (int i = 1; i < 4*1000000;i ++)
t[0][i] = inf, t[1][i] = -inf;
for (int i = 1; i <= q; i++) {
char c;
int l,r;
cin >> c >> l >> r;
if (c == 'A') {
cnt[{l,r}].pb(i);
L.insert(l);
R.insert(r);
AR[l].insert(r);
AL[r].insert(l);
}else {
qer(1,1,q,cnt[{l,r}].back(),i-1,l,r);
cnt[{l,r}].pop_back();
if (cnt[{l,r}].empty())
cnt.erase({l,r});
// query.push_back({cnt[{l,r}].back(),i})
AL[r].erase(AL[r].find(l));
AR[l].erase(AR[l].find(r));
// AL[r].erase(find(all(AL[r]),l));
// AR[l].erase(find(all(AR[l]),r));
L.erase(L.find(l));
R.erase(R.find(r));
}
l = *L.rbegin();
r = *R.begin();
int len = max(0,r - l);
if (len) {
int l1 = l, r1 = r;
r = *AR[l1].begin();
l = *AL[r1].rbegin();
ANS[i] = r-l;
// cout << r - l <<'\n';
}else {
F[i] = 1;
}}
for (auto&i : cnt) {
for (int j : i.second)
qer(1,1,q,j,q,i.fi.fi,i.fi.se);
}
dfs(1,1,q);
for (int i = 1; i <= q; i++)
cout << ANS[i] <<'\n';
}
Compilation message
grader.c: In function 'int main()':
grader.c:25:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
25 | while(res != 1);
| ^~~~~
grader.c:26:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
26 | res = fscanf(f, "%d", &C);
| ^~~
grader.c:27:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
27 | while(res != 1);
| ^~~~~
grader.c:28:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
28 | res = fscanf(f, "%d", &N);
| ^~~
game.cpp:257:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
257 | main() {
| ^
/tmp/ccawCE6h.o: In function `main':
game.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccQbNEmp.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccQbNEmp.o: In function `main':
grader.c:(.text.startup+0x7d): undefined reference to `init'
grader.c:(.text.startup+0xd8): undefined reference to `calculate'
grader.c:(.text.startup+0x142): undefined reference to `update'
collect2: error: ld returned 1 exit status
