//this solution is referred from comment of 300iq:
//https://codeforces.com/blog/entry/74871?#comment-590823
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define X first
#define Y second
const int N = 2e6 + 5;
typedef pair<int,int> ii;
typedef pair<int,ii> pii;
struct Node {
Node *l, *r;
Node *par;
ii key;
int pri, nCh;
int lzX, lzY;
Node(int x = 0,int y = 0) : l(0), r(0), par(0), key(ii(x,y)), pri(rand() << 16 ^ rand()), nCh(1), lzX(-1), lzY(-1) {}
} *p[N];
int Siz(Node *x) {
if (x) return x -> nCh;
else return 0;
}
void app(Node *x,int a,int b) {
if (a >= 0) (x -> key).X = x -> lzX = a;
if (b >= 0) (x -> key).Y = x -> lzY = b;
}
void pull(Node *x) {
x -> nCh = 1;
x -> nCh += Siz(x -> l);
x -> nCh += Siz(x -> r);
if (x -> l) x -> l -> par = x;
if (x -> r) x -> r -> par = x;
}
void push(Node *x) {
if (x -> l) app(x -> l,x -> lzX,x -> lzY);
if (x -> r) app(x -> r,x -> lzX,x -> lzY);
x -> lzX = -1;
x -> lzY = -1;
}
Node *join(Node *x,Node *y) {
if (!x) return y;
if (!y) return x;
if (x -> pri > y -> pri) {
push(x); x -> r = join(x -> r,y);
pull(x); return x;
}
else {
push(y); y -> l = join(x,y -> l);
pull(y); return y;
}
}
void split(Node *x,Node*&l,Node*&r,ii v) {
if (!x) {
l = r = 0;
return;
}
push(x);
if (v.X < (x -> key).X) { split(x -> l,l,x -> l,v); pull(r = x); return; }
if (v.Y < (x -> key).Y) { split(x -> l,l,x -> l,v); pull(r = x); return; }
split(x -> r,x -> r,r,v);
pull(l = x);
}
vector<ii> vec;
void dfs(Node *x) {
if(!x) return;
dfs(x -> l); vec.pb(x -> key);
dfs(x -> r);
}
struct Group {
Node *Rt;
int x, y;
};
bool operator < (const Group&a,const Group&b) {
ii tmp1(-a.y,a.Rt -> pri);
ii tmp2(-b.y,b.Rt -> pri);
return tmp1 < tmp2;
}
priority_queue<Group> pq[N];
int tr[N << 2];
#define lch i << 1
#define rch i << 1 | 1
void upd(int i,int l,int r,int p) {
if (l > p) return;
if (r < p) return;
if (l == r) {
if (pq[l].size()) tr[i] = pq[l].top().y;
else tr[i] = 1e9 + 7;
return;
}
int m = (l + r) / 2;
upd(lch,l,m,p); ++m;
upd(rch,m,r,p);
tr[i] = min(tr[lch],tr[rch]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
srand(time(NULL));
int n; cin >> n;
int m; cin >> m;
int q; cin >> q;
vector<pii> Que;
vector<int> val;
for(int i = 0 ; i < m ; ++i) {
int x; cin >> x;
int y; cin >> y;
Que.pb(4,ii(x,y));
val.pb(x);
}
for(int i = 0 ; i < q ; ++i) {
int t; cin >> t;
int x; cin >> x;
int y = n - x;
if (t == 4) cin >> y;
if (t == 2) swap(x,y);
Que.pb(t,ii(x,y));
if (t != 1)
val.pb(x);
}
sort(all(val));
val.erase(unique(all(val)),val.end());
auto add = [&](Node *R) {
if(!R) return;
Group G;
G.Rt = R;
while (R -> l)
push(R),
R = R -> l;
G.x = (R -> key).X;
G.y = (R -> key).Y;
int p = upper_bound(all(val),G.x) - val.begin();
pq[p].push(G);
upd(1,1,sz(val),p);
};
fill(tr + 1,tr + 4 * sz(val),1e9 + 7);
int tot = 0;
for(pii T : Que) {
int t = T.X;
int x = T.Y.X;
int y = T.Y.Y;
if (t == 1) {
vector<Node*> Path;
for(Node* a = p[x] ; a -> par ; Path.pb(a = a -> par)); reverse(all(Path));
for(Node* a : Path) push(a);
cout << (p[x] -> key).X << " ";
cout << (p[x] -> key).Y << "\n";
continue;
}
if (t == 4) {
add(p[++tot] = new Node(x,y));
continue;
}
vector<Node*> tmp;
while (tr[1] <= y) {
int i = 1;
int l = 1;
int r = sz(val);
while (l < r) {
int m = (l + r) / 2;
if (tr[lch] <= y) i = lch, r = m;
else i = rch, l = m + 1;
}
if (val[l - 1] > x)
break;
while (pq[l].size()) {
if(pq[l].top().y > y)
break;
Group G = pq[l].top(); pq[l].pop();
Node *a;
Node *b;
split(G.Rt,a,b,ii(x,y)); add(b);
if (a) a -> par = 0;
if (b) b -> par = 0;
assert(a);
tmp.pb(a);
}
upd(1,1,sz(val),l);
}
sort(all(tmp),[&](Node *a,Node *b) {
return Siz(a) > Siz(b);
});
for(Node *a : tmp) {
if (t == 2) app(a,x,-1);
if (t == 3) app(a,-1,y);
}
Node *Rt = 0;
for(Node *a : tmp) {
if (Siz(Rt) < Siz(a))
swap(Rt,a);
vec.clear();
dfs(a);
for(ii e : vec) {
Node *x;
Node *y;
split(a,x,a,e); assert(x && x -> key == e);
split(Rt,Rt,y,e);
Rt = join(Rt,x);
Rt = join(Rt,y);
}
}
add(Rt);
}
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:191:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(Node* a = p[x] ; a -> par ; Path.pb(a = a -> par)); reverse(all(Path));
^~~
sweeping.cpp:191:69: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(Node* a = p[x] ; a -> par ; Path.pb(a = a -> par)); reverse(all(Path));
^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
128380 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 |
1329 ms |
307404 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 |
1097 ms |
307820 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 |
1097 ms |
307820 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 |
115 ms |
128380 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
