#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int inf = 1e9 + 9;
const int nmax = 1e6 + 1;
template<typename T>
struct AINT {
vector<T> aint;
int n;
void init(int n_) {
n = n_;
aint.resize(n * 2 + 5, T());
}
template<class CB> void walk(CB&& cb) { walk(cb, 1, n); }
template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, 1, n); }
template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
walk(cb, l, r, L, cl, mid);
walk(cb, l, r, R, mid + 1, cr);
aint[node].pull(aint[L], aint[R]);
}
};
namespace DS {
auto byL = [](pii a, pii b) { return a.first < b.first || (a.first == b.first && a.second > b.second); };
auto byR = [](pii a, pii b) { return a.second < b.second || (a.second == b.second && a.first > b.first); };
multiset<pii, decltype(byL)> sortL(byL);
multiset<pii, decltype(byR)> sortR(byR);
struct segm {
int l, r;
segm(): l(-inf * 2), r(inf * 2) {;}
void pull(const segm& a, const segm& b) { l = max(a.l, b.l); r = min(b.r, a.r); }
};
AINT<segm> aint;
vector<int> ans;
vector<pair<int, segm>> rollback;
vector<pii> efectiv;
void insert(int l, int r) {
efectiv.emplace_back(l, r);
efectiv.emplace_back(-1, -1);
sortL.insert(pii{l, r});
sortR.insert(pii{l, r});
ans.push_back(ans.empty()? inf : ans.back());
aint.walk([&](segm& val, int cl, int cr) {
//cerr << cl << ' ' << cr << '\t' << val.l << ' ' << val.r << '\t' << l << ' ' << r << '\n';
ans.back() = min(ans.back(), r - val.l); return 0;
}, 1, l);
aint.walk([&](segm& val, int cl, int cr) {
ans.back() = min(ans.back(), val.r - l); return 0;
}, r, nmax);
aint.walk([&](segm& val, int cl, int cr) {
rollback.emplace_back(cl, val);
val.r = min(val.r, r);
return 0;
}, l, l);
aint.walk([&](segm& val, int cl, int cr) {
rollback.emplace_back(cl, val);
ans.emplace_back(ans.back());
val.l = max(val.l, l);
return 0;
}, r, r);
assert(ans.size() == rollback.size());
}
int time() { return sz(rollback); }
void pop() {
auto [l, r] = efectiv.back();
if(l != -1 && r != -1) sortL.erase(sortL.find(pii{l, r})), sortR.erase(sortR.find(pii{l, r}));
aint.walk([&](segm& val, int cl, int cr) {
val = rollback.back().second;
rollback.pop_back();
ans.pop_back();
return 0;
}, rollback.back().first, rollback.back().first);
}
int query() {
//for(auto [a, b] : sortL) cerr << a << ' ' << b << '\t';
//cerr << "--\n";
if(ans.empty() || ans.back() >= inf) {
auto a = *sortL.rbegin(), b = *sortR.begin();
return max(b.second, a.second) - min(b.first, a.first);
}
return ans.back();
}
}
int started = 0;
struct memory {
vector<pii> values;
int enter_time;
void pull(const memory& a, const memory& b) {
if(!started) return;
while(DS::time() > enter_time) DS::pop();
}
};
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n;
map<pii, vector<int>> still;
vector<pii> segms;
vector<pii> times;
for(int i = 1; i <= n; i++) {
char ch;
cin >> ch;
if(ch == 'A') {
int l, r;
cin >> l >> r;
segms.emplace_back(l, r);
times.emplace_back(i, n);
still[pii{l, r}].emplace_back(sz(segms) - 1);
}
else {
int l, r;
cin >> l >> r;
auto t = still[pii{l, r}].back();
still[pii{l, r}].pop_back();
times[t].second = i - 1;
}
}
AINT<memory> foroper;
foroper.init(n);
DS::aint.init(nmax);
for(int i = 0; i < sz(segms); i++) {
foroper.walk([&](memory& val, int cl, int cr) {
val.values.emplace_back(segms[i]);
return 0;
}, times[i].first, times[i].second);
}
started = 1;
foroper.walk([&](memory& val, int cl, int cr) {
val.enter_time = DS::time();
for(auto [a, b] : val.values) DS::insert(a, b);
//cerr << '\t' << cl << ' ' << cr << '\n';
//for(auto [a, b] : val.values) cerr << a << ' ' << b <<'\t';
//cerr << "\n--\n";
if(cl != cr) return 1;
cout << DS::query() << '\n';
while(DS::time() > val.enter_time) DS::pop();
return 0;
});
return 0;
}
/**
Istenem! Nu poate fi real.
-- Surse verificate
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16216 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
16220 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16216 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
16220 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16216 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
16220 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2360 ms |
283768 KB |
Output is correct |
| 2 |
Correct |
2319 ms |
282460 KB |
Output is correct |
| 3 |
Correct |
4985 ms |
574588 KB |
Output is correct |
| 4 |
Correct |
4828 ms |
572888 KB |
Output is correct |
| 5 |
Correct |
6219 ms |
708124 KB |
Output is correct |
| 6 |
Correct |
5986 ms |
708904 KB |
Output is correct |
| 7 |
Execution timed out |
7115 ms |
388248 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16216 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
16220 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
