// 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;
struct node{
node *L, *R;
int sz;
pi4 val;
pii mn;
node(pi4 _val){
L = R = 0, sz = 1;
val =_val;
mn = {val.S.F + val.S.S, val.F.F};
}
};
void bld(node* a){
a->sz = (a->L ? a->L->sz : 0) + (a->R ? a->R->sz : 0) + 1;
a->mn = min({ a->L ? a->L->mn : (pii){inf, inf}, a->R ? a->R->mn : (pii){inf, inf}, (pii){a->val.S.F + a->val.S.S, a->val.F.F} });
}
node* merge(node* a, node* b){
if(!a)
return b;
if(!b)
return a;
if( ( rand() % ((a->sz) + (b->sz)) ) < (a->sz) ){
a->R = merge(a->R, b);
bld(a);
return a;
}
else{
b->L = merge(a, b->L);
bld(b);
return b;
}
}
pair<node*, node*> split(node *rt, int x){
if(!rt)
return {0, 0};
if(rt->val.F.F >= x){
auto p = split(rt->L, x);
rt->L = p.S;
bld(rt);
return {p.F, rt};
}
else{
auto p = split(rt->R, x);
rt->R = p.F;
bld(rt);
return {rt, p.S};
}
}
void print(node *rt){
if(!rt)
return;
print(rt->L);
cout << "[ "<< (rt->val.F.F) << " " << rt->val.F.S << " " << rt->mn.F << " " << rt->mn.S << "] "<< " ";
print(rt->R);
}
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;
node* rt;
void restart(){
mp.clear();
rt = 0;
ins({0, N}, {0, 0});
}
pii color(pii p){
auto IT1 = --mp.upper_bound({p.F, inf});
auto IT2 = --mp.upper_bound({N - p.S, inf});
int L = IT1->F.F, R = IT2->F.F + 1;
auto [A, B] = split(rt, L);
auto [C, D] = split(B, R);
pii ans = mp.lower_bound( {C->mn.S, -1} )->F;
rt = merge(A, merge(C, D));
return ans;
}
void ins(pii a, pii b){
assert(mp.count(a) == 0);
mp[a] = b;
auto [A, B] = split(rt, a.F);
rt = merge(A, merge(new node({a, b}), B));
}
void era(pii a){
mp.erase(a);
auto [A, B] = split(rt, a.F);
auto [C, D] = split(B, a.F + 1);
assert(C);
rt = merge(A, D);
}
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;
era(it->F);
if(!is){
pii A = {L, x}, B = {x + 1, R};
ins(A, p);
if(B.F <= B.S)
ins(B, {B.F, p.S});
}
else{
pii A = {L, x - 1}, B = {x, R};
ins(B, p);
if(A.F <= A.S)
ins(A, {p.F, N - A.S});
}
}
pii calc(pii p){
pii s = color(p);
pii A = mp[s], B = trans(s), C = trans2(s);
assert(A.F <= p.F && A.S <= p.S && p.F <= B.F && p.S <= B.S);
return {max(C.F, p.F), max(C.S, p.S)};
}
};
const int Log = 22;
//bigTraingle tr[Log];
//vector<int> ids[Log];
//int who[maxn];
bigTraingle tr;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
srand(time(0));
int m, q;
cin >> N >> m >> q;
vector<pii> p;
/* for(int i = 0; i < Log; i++){
tr[i].restart();
if(bit(m, i)){
for(int j = 0; j < (1<<i); j++){
int x, y;
cin >> x >> y;
who[sz(p)] = i;
ids[i].PB(sz(p));
p.PB({x, y});
}
}
}*/
tr.restart();
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
p.PB({x, y});
}
while(q--){
int task;
cin >> task;
if(task == 1){
int id;
cin >> id;
--id;
// pii ans = tr[who[id]].calc(p[id]);
pii ans = tr.calc(p[id]);
cout << ans.F << " " << ans.S << "\n";
}
if(task == 2){
int l;
cin >> l;
/* for(int i = 0; i < Log; i++)
if(!ids[i].empty())
tr[i].add(l, 1);*/
tr.add(l, 1);
}
if(task == 3){
int l;
cin >> l;
/* for(int i = 0; i < Log; i++)
if(!ids[i].empty())
tr[i].add(l, 0);*/
tr.add(l, 0);
}
if(task == 4){
int x, y;
cin >> x >> y;
/* vector<int> vv;
vv.PB(sz(p));
p.PB({x, y});
int pt = 0;
while(!ids[pt].empty()){
for(int x : ids[pt])
vv.PB(x), p[x] = tr[pt].calc(p[x]);
ids[pt].clear();
tr[pt].restart();
pt++;
}
swap(ids[pt], vv);
for(int x : ids[pt]){
who[x] = pt;
}*/
assert(0);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
163 ms |
8708 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8830 ms |
110604 KB |
Output is correct |
| 2 |
Correct |
9025 ms |
110304 KB |
Output is correct |
| 3 |
Correct |
6736 ms |
109664 KB |
Output is correct |
| 4 |
Correct |
6429 ms |
110188 KB |
Output is correct |
| 5 |
Correct |
9231 ms |
110176 KB |
Output is correct |
| 6 |
Correct |
9554 ms |
110176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8830 ms |
110604 KB |
Output is correct |
| 2 |
Correct |
9025 ms |
110304 KB |
Output is correct |
| 3 |
Correct |
6736 ms |
109664 KB |
Output is correct |
| 4 |
Correct |
6429 ms |
110188 KB |
Output is correct |
| 5 |
Correct |
9231 ms |
110176 KB |
Output is correct |
| 6 |
Correct |
9554 ms |
110176 KB |
Output is correct |
| 7 |
Correct |
8296 ms |
110484 KB |
Output is correct |
| 8 |
Correct |
8547 ms |
110684 KB |
Output is correct |
| 9 |
Correct |
7993 ms |
110220 KB |
Output is correct |
| 10 |
Correct |
6921 ms |
109920 KB |
Output is correct |
| 11 |
Correct |
6399 ms |
110304 KB |
Output is correct |
| 12 |
Correct |
9434 ms |
110480 KB |
Output is correct |
| 13 |
Correct |
9529 ms |
110448 KB |
Output is correct |
| 14 |
Correct |
509 ms |
66296 KB |
Output is correct |
| 15 |
Correct |
627 ms |
22500 KB |
Output is correct |
| 16 |
Correct |
8318 ms |
110684 KB |
Output is correct |
| 17 |
Correct |
9883 ms |
110320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
