Submission #217054

#TimeUsernameProblemLanguageResultExecution timeMemory
217054theStaticMindNew Home (APIO18_new_home)C++14
5 / 100
5059 ms146524 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 #define int long long int using namespace std; #define rand() (1ll * rand() * rand() + rand() + 1) struct Node{ int left = 0, right = 0; int mx = -INF, val = -INF; int key = 0, prior = 0; bool operator<(Node& A){ return key < A.key || (key == A.key && val < A.val); } } node[500000]; int new_node(int k, int v){ static int ind = 1; node[ind].key = k; node[ind].val = node[ind].mx = v; node[ind].prior = rand(); return ind++; } struct Treap{ int root = 0; void up(int j){ if(!j)return; int l = node[j].left, r = node[j].right; node[j].mx = max(node[j].val, max(node[l].mx, node[r].mx)); } void split(int j, Node& v, int& l, int& r){ if(!j) l = r = 0; else if(node[j] < v) split(node[j].right, v, node[j].right, r), l = j; else split(node[j].left, v, l, node[j].left), r = j; up(j); } void merge(int& j, int l, int r){ if(!l || !r) j = max(l, r); else if(node[l].prior > node[r].prior) merge(node[l].right, node[l].right, r), j = l; else merge(node[r].left, l, node[r].left), j = r; up(j); } void insert(int& j, int i){ if(!j) j = i; else if(node[i].prior > node[j].prior) split(j, node[i], node[i].left, node[i].right), j = i; else{ if(node[i] < node[j]) insert(node[j].left, i); else insert(node[j].right, i); } up(j); } void erase(int& j, Node& v){ assert(j); if(node[j].key == v.key && node[j].val == v.val) merge(j, node[j].left, node[j].right); else if(v < node[j]) erase(node[j].left, v); else erase(node[j].right, v); up(j); } void add(int k, int v){ insert(root, new_node(k, v)); } void remove(int k, int v){ erase(root, node[new_node(k, v)]); } int query(int x, int y){ int a, b, c; Node t; t.key = x; t.val = -INF; split(root, t, a, b); t.key = y, t.val = INF; split(b, t, b, c); int ret = node[b].mx; merge(root, a, b); merge(root, root, c); return ret; } } Ltree, Rtree; struct Store{ int x, type, tl, tr; }; struct Query{ int x, time, id; }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); srand(time(NULL)); int n, k, q; cin >> n >> k >> q; vector<Store> X, Y; vector<Query> Q; vector<int> ans(q); vector<int> cnt(k + 1, 0); multiset<int> K[k + 1]; int c = k; for(int i = 1; i <= k; i++) { K[i].insert(-2e9), K[i].insert(2e9); Rtree.add(0, 2e9); Ltree.add(0, 2e9); } for(int i = 0; i < n; i++){ int a, b, c, d; cin >> a >> b >> c >> d; a*=2; X.pb({a, b, c, d}); Y.pb({a, b, c, d}); } for(int i = 0; i < q; i++){ int a, b; cin >> a >> b; a*=2; Q.pb({a, b, i}); } sort(all(X), [&](Store& A, Store& B){return A.tl < B.tl;}); sort(all(Y), [&](Store& A, Store& B){return A.tr < B.tr;}); sort(all(Q), [&](Query& A, Query& B){return A.time < B.time;}); int a = 0, b = 0; for(auto& curr : Q){ while(a < n && X[a].tl <= curr.time){ int t = X[a].type, x = X[a].x; if(++cnt[t] == 1) c--; auto next = K[t].upper_bound(x); auto prev = std::prev(next); int mid = (*next + *prev) / 2; Rtree.remove(mid, -*prev); Ltree.remove(mid, *next); mid = (*prev + x) / 2; Rtree.add(mid, -*prev); Ltree.add(mid, x); mid = (x + *next) / 2; Rtree.add(mid, -x); Ltree.add(mid, *next); K[t].insert(x); a++; } while(b < n && Y[b].tr < curr.time){ int t = Y[b].type, x = Y[b].x; if(--cnt[Y[b].type] == 0) c++; K[t].erase(K[t].find(x)); auto next = K[t].upper_bound(x); auto prev = std::prev(next); int mid = (*prev + x) / 2; Rtree.remove(mid, -*prev); Ltree.remove(mid, x); mid = (x + *next) / 2; Rtree.remove(mid, -x); Ltree.remove(mid, *next); mid = (*next + *prev) / 2; Rtree.add(mid, -*prev); Ltree.add(mid, *next); b++; } if(c > 0){ ans[curr.id] = -2; continue; } ans[curr.id] = max(Rtree.query(curr.x, INF) + curr.x, Ltree.query(-INF, curr.x) - curr.x); } for(int i = 0; i < q; i++) cout << ans[i] / 2 << ' '; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...