Submission #217270

#TimeUsernameProblemLanguageResultExecution timeMemory
217270theStaticMindNew Home (APIO18_new_home)C++14
57 / 100
5078 ms263548 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) int S; struct MaxSeg{ vector<int> seg; void build(){ S = (1 << (int)ceil(log2(sz(seg)))); int l = S - sz(seg); for(int i = 0; i < l; i++) seg.pb(-INF); reverse(all(seg)); for(int i = 1; i < sz(seg); i += 2) seg.pb(max(seg[i - 1], seg[i])); seg.pb(0); reverse(all(seg)); } MaxSeg(int n){ seg = vector<int>(n, -INF); build(); } int query(int a, int b, int j = 1, int l = 0, int r = S - 1){ if(r < a || b < l) return -INF; if(a <= l && r <= b) return seg[j]; return max(query(a,b,j*2,l,(l+r)/2), query(a,b,j*2+1,(l+r)/2+1,r)); } void update(int j, int v){ j += S; seg[j] = v; j /= 2; while(j != 0){ seg[j] = max(seg[j * 2], seg[j * 2 + 1]); j /= 2; } } }; struct Store{ int x, type, tl, tr, id; }; struct Query{ int x, time, id; }; struct Event{ int t, l, r, i, id; Event(int a, int b, int c, int d, int e){ t=a,l=b,r=c,i=d,id=e; } int mid(){ return (l + r) / 2; } bool operator<=(Event& A){ if(mid() < A.mid()) return true; if(mid() == A.mid()){ if(id <= A.id) return true; } return false; } } ; vector<Event> E; int ind = 0; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(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); map<int, int> K[k + 1]; int c = k; for(int i = 1; i <= k; i++) { K[i][2e9]++, K[i][-2e9]++; E.pb(Event(-1, -2e9, 2e9, 1, i)); } 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, i}); Y.pb({a, b, c, d, i}); } 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--; if(!K[t].count(x)){ auto next = K[t].upper_bound(x); auto prev = std::prev(next); E.pb(Event(X[a].tl, prev->first, next->first, 0, t)); E.pb(Event(X[a].tl, prev->first, x, 1, t)); E.pb(Event(X[a].tl, x, next->first, 1, t)); } K[t][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++; if(K[t][x] == 1){ K[t].erase(x); auto next = K[t].upper_bound(x); auto prev = std::prev(next); E.pb(Event(Y[b].tr+1, prev->first, x, 0, t)); E.pb(Event(Y[b].tr+1, x, next->first, 0, t)); E.pb(Event(Y[b].tr+1, prev->first, next->first, 1, t)); } else{ K[t][x]--; } b++; } if(c > 0){ ans[curr.id] = -2; continue; } } MaxSeg L(sz(E)), R(sz(E)); a = 0; vector<int> seq; for(int i = 0; i < sz(E); i++) seq.pb(i); sort(all(seq), [&](int x, int y){return E[x] <= E[y];}); auto lower = [&](Event x){ int l = 0, r = sz(seq) - 1; int ret = 0; while(l <= r){ int mid = (l + r) / 2; if(x <= E[seq[mid]]){ ret = mid; r = mid - 1; } else l = mid + 1; } return ret; }; int w; for(auto& curr : Q){ while(a < sz(E) && E[a].t <= curr.time){ w = lower(E[a]); if(E[a].i){ R.update(w, -E[a].l); L.update(w, E[a].r); } else{ R.update(w, -INF); L.update(w, -INF); } a++; } if(ans[curr.id] == -2){ continue; } int x = curr.x; w = lower(Event(0,x,x,1,-1)); ans[curr.id] = max(L.query(0, w - 1) - x, R.query(w, S-1) + 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...