#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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*4];
int l1,r1,QL,QR;
void qer(int v,int tl,int tr) {
if (l1 > tr || r1 < tl) return;
if (l1 <= tl && r1 >= tr) {
Q[v].pb({QL,QR});
return;
}
int tm = (tl + tr)/2;
qer(v*2,tl,tm);
qer(v*2+1,tm+1,tr);
}
int cans=INT_MAX;
int t[2][4*N],timer;
int *H[100000000];
int val[100000000];
void change(int&x,int c) {
H[++timer] = &x;
val[timer] = x;
x = c;
}
void rollback() {
(*H[timer--]) = val[timer];
}
bool type;
int VAL,pos,L,R;
int BIT[2][N];
const int REV = 1e6;
void add(int v=1,int tl=1,int tr=1e6) {
if (tl == tr) {
if (!type) {
if (VAL < t[0][v])
change(t[0][v],VAL);
}
else if (VAL > t[1][v])
change(t[1][v],VAL);
return;
}
int tm = (tl + tr)/2;
if (pos <= tm)
add(v*2,tl,tm);
else add(v*2+1,tm+1,tr);
if (!type)
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]));
}
void add1(int pos,int val,bool type) {
if (type)
for (;pos < 1e6; pos += pos&-pos)
if (BIT[1][pos] < val)
change(BIT[1][pos],val);
else {
for (;pos < 1e6; pos += pos&-pos)
if (BIT[0][pos] > val)
change(BIT[0][pos],val);
}
}
int get1(int pos,bool type) {
if (type == 0) {
int s = inf;
for (;pos;pos -= pos&-pos)
s = min(s,BIT[0][REV - pos]);
return s;
}else {
int s = -inf;
for (;pos;pos -= pos&-pos)
s = max(s,BIT[1][pos]);
return s;
}
}
int get(int v=1,int tl=1,int tr=1e6) {
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)
return min(get(v*2,tl,tm),get(v*2+1,tm+1,tr));
else return max(get(v*2,tl,tm),get(v*2+1,tm+1,tr));
}
int L1=-inf,R1=inf,AR1[N],AL1[N],HANS=inf;
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;
if (R1 > r)
change(R1,r);
if (L1 < l)
change(L1,l);
if (AR1[l] > r)
change(AR1[l],r);
if (AL1[r] < l)
change(AL1[r],l);
{
int l2 = L1;
int r2 = R1;
int len = max(0,r2 - l2);
if (len) {
int r3 = AR1[l2];
int l3 = AL1[r2];
change(HANS,r3-l3);
pos = l;
VAL = r;
type = 0;
add1(REV - pos,VAL,0); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
add();
pos = r;
VAL = l;
type = 1;
add1(pos,VAL,1);
continue;
}
}
L = r;
R = 1e6;
type = 0;
if (cans > r - l) {
cans = min(cans, -l + get1(REV - L,0));
}
L = 1;
R = l;type = 1;
if (cans > r - l)
cans = min(cans, r - get1(R,1));
pos = l;
VAL = r;
type = 0;
add1(REV-pos,VAL,0); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
// add1(REV - pos,r,0);
add();
pos = r;
VAL = l;
type = 1;
add1(pos,VAL,1);
// add1(pos,VAL,1);
}
if (tl != tr) {
int tm = (tl + tr)/2;
dfs(v*2,tl,tm);
dfs(v*2+1,tm+1,tr);
}else {
if (cans > 1000000)
ANS[tl] = HANS;
else
ANS[tl] = cans;
}
while(start_time != timer)
rollback();
cans = in_ans;
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin >> q;
for (int i = 0; i < N; i++)
AR1[i] = BIT[0][i] = inf,AL1[i] = BIT[1][i]=-inf;
for (int i = 0; i < 4*N;i ++)
t[0][i] = inf, t[1][i] = -inf;
vector<pair<pii,char> > query(q+1);
vector<pii> t(q);
for (int i = 1; i <= q; i++) {
char c;
int l,r;
cin >> c >> l >> r;
query[i] = {{l,r},c};
t[i-1] = {l,r};
}
sort(all(t));
t.resize(unique(all(t)) - t.begin());
map<pii,int> ID;
for (int i = 0; i < t.size(); i++) {
ID[t[i]] = i;
}
set<int> cnt[1000005];
for (int i = 1; i <= q; i++) {
char c= query[i].se;
int l = query[i].fi.fi;
int r = query[i].fi.se;
int id = ID[{l,r}];
if (c == 'A')
cnt[id].insert(i);
else {
l1=*cnt[id].begin();
r1 = i-1;
QL= l;
QR = r;
qer(1,1,q);
cnt[id].erase(cnt[id].begin());
}
F[i] = 1;
}
for (int i= 0; i < t.size(); i++)
for (int j : cnt[i]) {
l1 = j;
r1 = q;
QL = t[i].fi;
QR = t[i].se;
qer(1,1,q);
}
dfs(1,1,q);
for (int i = 1; i <= q; i++)
cout << ANS[i] <<'\n';
}
Compilation message
Main.cpp: In function 'void rollback()':
Main.cpp:38:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
38 | (*H[timer--]) = val[timer];
| ~~~~~^~
Main.cpp:38:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
Main.cpp: In function 'void add1(int, int, bool)':
Main.cpp:65:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
65 | if (type)
| ^
Main.cpp: In function 'int get1(int, bool)':
Main.cpp:78:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
78 | for (;pos;pos -= pos&-pos)
| ^~~
Main.cpp:80:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
80 | return s;
| ^~~~~~
Main.cpp:83:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
83 | for (;pos;pos -= pos&-pos)
| ^~~
Main.cpp:85:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
85 | return s;
| ^~~~~~
Main.cpp: At global scope:
Main.cpp:174:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
174 | main() {
| ^
Main.cpp: In function 'int main()':
Main.cpp:196:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for (int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
Main.cpp:217:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for (int i= 0; i < t.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
188408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
188408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
188408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1296 ms |
317400 KB |
Output is correct |
| 2 |
Incorrect |
1203 ms |
312224 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
188408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
