// 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 = 1e6 + 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});
pii ANS = {inf, inf};
for(auto it = IT1; it != next(IT2); it++){
ANS = min(ANS, {it->S.F + it->S.S, it->F.F});
}
int L = IT1->F.F, R = IT2->F.F + 1;
auto [A, B] = split(rt, L);
auto [C, D] = split(B, R);
assert(C->mn == ANS);
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)};
}
};bigTraingle tr[20];
vector<int> ids[20];
int who[maxn];
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 < 20; 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});
}
}
}
while(q--){
int task;
cin >> task;
if(task == 1){
int id;
cin >> id;
--id;
pii ans = tr[who[id]].calc(p[id]);
cout << ans.F << " " << ans.S << "\n";
}
if(task == 2){
int l;
cin >> l;
for(int i = 0; i < 20; i++)
if(!ids[i].empty())
tr[i].add(l, 1);
}
if(task == 3){
int l;
cin >> l;
for(int i = 0; i < 20; i++)
if(!ids[i].empty())
tr[i].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;
}
}
}
return 0;
}
Compilation message
sweeping.cpp: In member function 'pii bigTraingle::color(pii)':
sweeping.cpp:102:7: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [A, B] = split(rt, L);
^
sweeping.cpp:103:7: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [C, D] = split(B, R);
^
sweeping.cpp: In member function 'void bigTraingle::ins(pii, pii)':
sweeping.cpp:114:7: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [A, B] = split(rt, a.F);
^
sweeping.cpp: In member function 'void bigTraingle::era(pii)':
sweeping.cpp:119:7: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [A, B] = split(rt, a.F);
^
sweeping.cpp:120:7: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [C, D] = split(B, a.F + 1);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
27 ms |
1784 KB |
Output is correct |
| 3 |
Correct |
5 ms |
640 KB |
Output is correct |
| 4 |
Correct |
26 ms |
1536 KB |
Output is correct |
| 5 |
Correct |
51 ms |
3064 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18026 ms |
128196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18078 ms |
147716 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18078 ms |
147716 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
27 ms |
1784 KB |
Output is correct |
| 3 |
Correct |
5 ms |
640 KB |
Output is correct |
| 4 |
Correct |
26 ms |
1536 KB |
Output is correct |
| 5 |
Correct |
51 ms |
3064 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 7 |
Execution timed out |
18026 ms |
128196 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
