// 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;
/*
struct node{
node *L, *R;
int mx;
node(){
L = R = 0;
mx = -1;
}
void add(int f, int s, int x, int l = 0, int r = inf){
if(f <= l && r <= s){
mx = max(mx, x);
return;
}
int mid = (l+r) >> 1;
if(s > l && mid > f){
if(L == 0)
L = new node();
L->add(f, s, x, l, mid);
}
if(s > mid && r > f){
if(R == 0)
R = new node();
R->add(f, s, x, mid, r);
}
}
int ask(int pos, int l = 0, int r = inf){
int mid = (l+r) >> 1;
if(pos < mid){
if(L == 0)
return mx;
return max(mx, L->ask(pos, l, mid));
}
else{
if(R == 0)
return mx;
return max(mx, R->ask(pos, mid, r));
}
}
};node* emp;
struct node2{
node2 *L, *R;
node* s;
node2(){
L = R = 0;
s = 0;
}
void add(int fx, int sx, int fy, int sy, int x, int l = 0, int r = inf){
if(fx <= l && r <= sx){
if(s == 0)
s = new node();
s->add(fy, sy, x);
return;
}
int mid = (l+r) >> 1;
if(sx > l && mid > fx){
if(L == 0)
L = new node2();
L->add(fx, sx, fy, sy, x, l, mid);
}
if(sx > mid && r > fx){
if(R == 0)
R = new node2();
R->add(fx, sx, fy, sy, x, mid, r);
}
}
int ask(int posx, int posy, int l = 0, int r = inf){
int mid = (l+r) >> 1;
if(posx < mid){
int ans = -1;
if(s)
ans = s->ask(posy);
if(L)
ans = max(ans, L->ask(posx, posy, l, mid));
return ans;
}
else{
int ans = -1;
if(s)
ans = s->ask(posy);
if(R)
ans = max(ans, R->ask(posx, posy, mid, r));
return ans;
}
}
};node2* emp2;
*/
struct node2{
vector<pii> X, Y;
vector<int> val;
void add(int fx, int sx, int fy, int sy, int x){
val.PB(x);
X.PB({fx, sx});
Y.PB({fy, sy});
}
int ask(int posx, int posy){
int ans = -1;
for(int i = 0; i < sz(val); i++){
if(X[i].F <= posx && posx < X[i].S && Y[i].F <= posy && posy < Y[i].S)
ans = max(ans, val[i]);
}
return ans;
}
};
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<pii> to;
node2* rt;
void restart(){
mp.clear();
to.clear();
rt = new node2();
ins({0, N}, {0, 0});
}
pii color(pii p){
int c = rt->ask(p.F, p.S);
return to[c];
}
void put(pii l, pii r, pii x){
rt->add(l.F, r.F + 1, l.S, r.S + 1, sz(to));
to.PB(x);
}
void ins(pii a, pii b){
mp[a] = b;
put(b, trans(a), a);
}
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};
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;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int m, q;
cin >> N >> m >> q;
vector<pii> p(m);
for(int i = 0; i < m; i++){
cin >> p[i].F >> p[i].S;
}
tr.restart();
while(q--){
int task;
cin >> task;
if(task == 1){
int id;
cin >> id;
pii ans = tr.calc(p[--id]);
cout << ans.F << " " << ans.S << "\n";
}
if(task == 2){
int l;
cin >> l;
tr.add(l, 1);
}
if(task == 3){
int l;
cin >> l;
tr.add(l, 0);
}
if(task == 4){
// int x, y;
// cin >> x >> y;
assert(0);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
640 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 |
162 ms |
11368 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 |
Execution timed out |
18066 ms |
22928 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18066 ms |
22928 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
