Submission #216750

#TimeUsernameProblemLanguageResultExecution timeMemory
216750combi1k1Sweeping (JOI20_sweeping)C++14
11 / 100
18062 ms187256 KiB
//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; push(x); 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); } 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); split(Rt,Rt,y,e); Rt = join(Rt,x); Rt = join(Rt,y); } } add(Rt); } }

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:193: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:193: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...