// 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;
const int maxn = 1e6 + 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 node{
node *L = 0, *R = 0;
int val = inf;
};
node* rt = new node();
void put(int pos, int x, int l = 0, int r = N+1, node *nw = rt){
if(r-l == 1){
nw->val = x;
return;
}
int mid = (l+r) >> 1;
if(pos < mid){
if(nw->L == 0)
nw->L = new node();
put(pos, x, l, mid, nw->L);
}
else{
if(nw->R == 0)
nw->R = new node();
put(pos, x, mid, r, nw->R);
}
nw->val = min(nw->L ? nw->L->val : inf, nw->R ? nw->R->val : inf);
}
int best(int f, int s, int l = 0, int r = N+1, node* nw = rt){
if(s <= l || r <= f)
return inf;
if(f <= l && r <= s)
return nw->val;
int mid = (l+r) >> 1;
int ans = inf;
if(nw->L)
ans = min(ans, best(f, s, l, mid, nw->L));
if(nw->R)
ans = min(ans, best(f, s, mid, r, nw->R));
return ans;
}
int choose(int f, int s, int x, int l = 0, int r = N+1, node* nw = rt){
if(s <= l || r <= f || nw->val > x)
return -1;
if(r-l == 1)
return l;
if(f <= l && r <= s){
int mid = (l+r) >> 1;
if(nw->L && nw->L->val == x)
return choose(f, s, x, l, mid, nw->L);
if(nw->R && nw->R->val == x)
return choose(f, s, x, mid, r, nw->R);
assert(0);
}
int mid = (l+r) >> 1;
int ans = -1;
if(nw->L)
ans = choose(f, s, x, l, mid, nw->L);
if(ans != -1)
return ans;
if(nw->R)
ans = choose(f, s, x, mid, r, nw->R);
return ans;
}
struct bigTraingle{
map<pii, pii> mp;
void restart(){
mp.clear();
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, val = best(L, R), pos = choose(L, R, val);
return mp.lower_bound( {pos, -1} )->F;
/*
int num = N + 10;
pii ans = {-1, -1};
for(auto it = IT1; it != next(IT2); it++)
if(it->S.F + it->S.S < num)
num = it->S.F + it->S.S, ans = it->F;
return ans;*/
}
void ins(pii a, pii b){
mp[a] = b;
put(a.F, b.F + b.S);
}
void era(pii a){
mp.erase(a);
put(a.F, inf);
}
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();
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1280 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
18712 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 |
14575 ms |
571476 KB |
Output is correct |
| 2 |
Correct |
11259 ms |
442600 KB |
Output is correct |
| 3 |
Correct |
8384 ms |
424508 KB |
Output is correct |
| 4 |
Correct |
8216 ms |
424908 KB |
Output is correct |
| 5 |
Correct |
13971 ms |
424816 KB |
Output is correct |
| 6 |
Correct |
13484 ms |
428964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14575 ms |
571476 KB |
Output is correct |
| 2 |
Correct |
11259 ms |
442600 KB |
Output is correct |
| 3 |
Correct |
8384 ms |
424508 KB |
Output is correct |
| 4 |
Correct |
8216 ms |
424908 KB |
Output is correct |
| 5 |
Correct |
13971 ms |
424816 KB |
Output is correct |
| 6 |
Correct |
13484 ms |
428964 KB |
Output is correct |
| 7 |
Correct |
10967 ms |
442688 KB |
Output is correct |
| 8 |
Correct |
11080 ms |
442588 KB |
Output is correct |
| 9 |
Correct |
11235 ms |
442608 KB |
Output is correct |
| 10 |
Correct |
9364 ms |
424560 KB |
Output is correct |
| 11 |
Correct |
8764 ms |
425048 KB |
Output is correct |
| 12 |
Correct |
13879 ms |
428852 KB |
Output is correct |
| 13 |
Correct |
12807 ms |
425092 KB |
Output is correct |
| 14 |
Correct |
283 ms |
4216 KB |
Output is correct |
| 15 |
Correct |
857 ms |
31300 KB |
Output is correct |
| 16 |
Correct |
14184 ms |
554092 KB |
Output is correct |
| 17 |
Correct |
11662 ms |
429068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1280 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
