Submission #210049

#TimeUsernameProblemLanguageResultExecution timeMemory
210049Alexa2001New Home (APIO18_new_home)C++17
0 / 100
5113 ms205396 KiB
#include <bits/stdc++.h> using namespace std; const int lim = 2e8+2, Nmax = 3e5 + 5, Lim = 2 * Nmax; typedef pair<int,int> Pair; int n, k, q; int x[Nmax], tip[Nmax], start[Nmax], finish[Nmax], ans[Nmax]; int X[Nmax], T[Nmax]; vector<Pair> v[Nmax]; vector<int> ord; struct modif { int tmp, l, r, add; }; vector<modif> op; auto inv_sort = [](Pair a, Pair b) { return a > b; }; #define left_son (node<<1) #define right_son ((node<<1)|1) #define mid ((st+dr)>>1) class SegmentTree { vector<Pair> o; int n; int a[Lim<<2]; map<Pair, int> In, Out; void update(int node, int st, int dr, int pos, int add) { if(st == dr) { if(add == 1) a[node] = o[pos].second; else a[node] = (1<<30); return; } if(pos <= mid) update(left_son, st, mid, pos, add); else update(right_son, mid+1, dr, pos, add); a[node] = min(a[left_son], a[right_son]); } int query(int node, int st, int dr, int pos) { if(o[st].first < pos) return (1<<30); if(o[dr].first >= pos) return a[node]; int res1 = query(left_son, st, mid, pos), res2 = query(right_son, mid+1, dr, pos); return min(res1, res2); } public: void init(vector<Pair> &all) { o = all; n = all.size(); memset(a, 0x3f3f3f3f, sizeof(a)); } void update(modif el) { int pos; if(el.add == 1) { int nr = In[{el.r, el.l}]++; pos = lower_bound(o.begin(), o.end(), make_pair(el.r, el.l), inv_sort) - o.begin() + nr; } else { int nr = Out[{el.r, el.l}]++; pos = lower_bound(o.begin(), o.end(), make_pair(el.r, el.l), inv_sort) - o.begin() + nr; } update(1, 0, n-1, pos, el.add); } int query(int pos) { return pos - query(1, 0, n-1, pos); } } aint; void find_segments() { int i; for(i=1; i<=n; ++i) { v[tip[i]].push_back({start[i], +x[i]}); v[tip[i]].push_back({finish[i]+1, -x[i]}); } for(i=1; i<=k; ++i) { sort(v[i].begin(), v[i].end()); multiset<int> S; S.insert(-4*lim); S.insert(2*lim); op.push_back({0, -4*lim, 2*lim}); for(auto el : v[i]) if(el.second > 0) /// insert new store { int X = el.second; multiset<int> :: iterator it = S.insert(X); int X1, X2; X1 = *prev(it); X2 = *next(it); op.push_back({el.first, X1, (X1 + X2) / 2, -1}); op.push_back({el.first, X1, (X1 + X) / 2, +1}); op.push_back({el.first, X, (X + X2) / 2, +1}); } else { int X = -el.second; multiset<int> :: iterator it = S.find(X); int X1, X2; X1 = *prev(it); X2 = *next(it); S.erase(it); op.push_back({el.first, X1, (X1 + X2) / 2, +1}); op.push_back({el.first, X1, (X1 + X) / 2, -1}); op.push_back({el.first, X, (X + X2) / 2, -1}); } } } void prepare() { vector<Pair> all; for(auto it : op) if(it.add == 1) all.push_back({ it.r, it.l }); sort(all.begin(), all.end(), inv_sort); aint.init(all); } vector<int> sort_queries() { vector<int> ord(q); iota(ord.begin(), ord.end(), 1); sort(ord.begin(), ord.end(), [](int x, int y) { return T[x] < T[y]; }); return ord; } void sort_op() { sort(op.begin(), op.end(), [](modif a, modif b) { return a.tmp < b.tmp; }); } void change(int &x, int y) { if(x == -1) return; if(x < y) x = y; } void solve_queries(vector<int> &ord) { int p = 0; for(auto id : ord) { while(p<op.size() && op[p].tmp <= T[id]) aint.update(op[p]), p++; change(ans[id], aint.query(X[id]) / 2); } } void solve() { find_segments(); prepare(); sort_op(); solve_queries(ord); } void clr() { int i; for(i=1; i<=k; ++i) v[i].clear(); op.clear(); } void prec() { int i; vector<Pair> V; for(i=1; i<=n; ++i) { V.push_back({ start[i], tip[i] }); V.push_back({ finish[i]+1, -tip[i] }); } sort(V.begin(), V.end()); i = 0; int nr_dif = 0; vector<int> cnt(k+1,0); for(auto id : ord) { while(i < V.size() && V[i].first <= T[id]) { if(V[i].second > 0) { ++cnt[V[i].second]; if(cnt[V[i].second] == 1) ++nr_dif; } else { --cnt[-V[i].second]; if(cnt[-V[i].second] == 0) --nr_dif; } ++i; } if(nr_dif < k) ans[id] = -1; } } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin.tie(0); cin >> n >> k >> q; int i; for(i=1; i<=n; ++i) cin >> x[i] >> tip[i] >> start[i] >> finish[i]; for(i=1; i<=q; ++i) cin >> X[i] >> T[i]; for(i=1; i<=n; ++i) x[i] *= 2; for(i=1; i<=q; ++i) X[i] *= 2; ord = sort_queries(); prec(); solve(); clr(); for(i=1; i<=n; ++i) x[i] = lim - x[i]; for(i=1; i<=q; ++i) X[i] = lim - X[i]; solve(); for(i=1; i<=q; ++i) cout << ans[i] << '\n'; return 0; }

Compilation message (stderr)

new_home.cpp: In function 'void solve_queries(std::vector<int>&)':
new_home.cpp:186:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p<op.size() && op[p].tmp <= T[id])
               ~^~~~~~~~~~
new_home.cpp: In function 'void prec()':
new_home.cpp:226:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < V.size() && V[i].first <= T[id])
               ~~^~~~~~~~~~
#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...