// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii, pii> pi4;
const int maxn = 2e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int N;
pii trans(pii p){ // x1 x2
return {p.S, N - p.F};
}
pii trans2(pii p){ // x1 x2
return {p.F, N - p.S};
}
struct bigTraingle{
map<pii, pii> mp;
vector<pair<pii, int> > v;
int sp[21][maxn];
void restart(){
mp.clear();
mp[{0, N}] = {0, 0};
}
pii color(pii p){
int L = upper_bound(v.begin(), v.end(), (pair<pii, int>){{p.F, inf}, inf}) - v.begin() - 1;
int R = upper_bound(v.begin(), v.end(), (pair<pii, int>){{N - p.S, inf}, inf}) - v.begin();
assert(L < R);
int lg = 31 - __builtin_clz(R-L);
int A = sp[lg][L], B = sp[lg][R - (1<<lg)];
if(v[B].S < v[A].S)
A = B;
return v[A].F;
}
void add(int l, bool is){
int x = l, y = N - l;
if(is)
swap(x, y);
auto it = --mp.upper_bound({x, inf});
int L = it->F.F, R = it->F.S;
pii p = it->S;
mp.erase(it);
if(!is){
pii A = {L, x}, B = {x + 1, R};
mp[A] = p;
if(B.F <= B.S)
mp[B] = {B.F, p.S};
}
else{
pii A = {L, x - 1}, B = {x, R};
mp[B] = p;
if(A.F <= A.S)
mp[A] = {p.F, N - A.S};
}
}
pii calc(pii p){
pii s = color(p);
pii C = trans2(s);
return {max(C.F, p.F), max(C.S, p.S)};
}
void prepare(){
v.clear();
for(auto x : mp){
v.PB({x.F, x.S.F + x.S.S});
}
assert(sz(v));
int Log = 31 - __builtin_clz(sz(v));
for(int i = 0; i < sz(v); i++)
sp[0][i] = i;
for(int i = 1; i <= Log; i++){
for(int j = 0; j < sz(v); j++){
sp[i][j] = sp[i-1][j];
int k = j + (1<<(i-1));
if(k < sz(v) && v[sp[i-1][j]].S > v[sp[i-1][k]].S)
sp[i][j] = sp[i-1][k];
}
}
}
};
int LST[maxn];
vector<pii> conf, p, tell[maxn];
pii ans[maxn];
vector<int> tdo[4 * maxn];
void place(int f, int s, int x, int l = 0, int r = sz(conf) + 1, int id = 1){
if(f >= s || s <= l || r <= f)
return;
if(f <= l && r <= s){
tdo[id].PB(x);
return;
}
int mid = (l+r) >> 1;
place(f, s, x, l, mid, 2*id);
place(f, s, x, mid, r, 2*id+1);
}
bigTraingle tr;
void solve(int l = 0, int r = sz(conf) + 1, int id = 1){
if(r-l == 1){
for(pii x : tell[l]){
ans[x.S] = p[x.F];
}
}
if(r-l > 1){
int mid = (l+r) >> 1;
solve(l, mid, 2*id);
solve(mid, r, 2*id + 1);
}
if(r == sz(conf) + 1)
assert(tdo[id].empty());
if(tdo[id].empty())
return;
tr.restart();
for(int i = l; i < r; i++)
tr.add(conf[i].F, conf[i].S);
tr.prepare();
for(int i : tdo[id])
p[i] = tr.calc(p[i]);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int m, q;
cin >> N >> m >> q;
p.resize(m);
for(int i = 0; i < m; i++){
cin >> p[i].F >> p[i].S;
}
int Q = 0;
for(int i = 0; i < q; i++){
int task;
cin >> task;
if(task == 1){
int id;
cin >> id;
--id;
// tell[sz(conf)].PB({id, Q++});
// place(LST[id], sz(conf), id);
tr.restart();
for(int w = LST[id]; w < sz(conf); w++)
tr.add(conf[w].F, conf[w].S);
tr.prepare();
p[id] = tr.calc(p[id]);
ans[Q++] = p[id];
LST[id] = sz(conf);
}
if(task == 2){
int l;
cin >> l;
conf.PB({l, 1});
}
if(task == 3){
int l;
cin >> l;
conf.PB({l, 0});
}
if(task == 4){
int x, y;
cin >> x >> y;
LST[sz(p)] = sz(conf);
p.PB({x, y});
}
}
// solve();
for(int i = 0; i < Q; i++){
cout << ans[i].F << " " << ans[i].S << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
616 ms |
235800 KB |
Output is correct |
| 2 |
Correct |
369 ms |
235640 KB |
Output is correct |
| 3 |
Correct |
159 ms |
235384 KB |
Output is correct |
| 4 |
Correct |
632 ms |
235640 KB |
Output is correct |
| 5 |
Correct |
146 ms |
235512 KB |
Output is correct |
| 6 |
Correct |
311 ms |
235384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18091 ms |
243064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18102 ms |
242720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18102 ms |
242720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
616 ms |
235800 KB |
Output is correct |
| 2 |
Correct |
369 ms |
235640 KB |
Output is correct |
| 3 |
Correct |
159 ms |
235384 KB |
Output is correct |
| 4 |
Correct |
632 ms |
235640 KB |
Output is correct |
| 5 |
Correct |
146 ms |
235512 KB |
Output is correct |
| 6 |
Correct |
311 ms |
235384 KB |
Output is correct |
| 7 |
Execution timed out |
18091 ms |
243064 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
