Submission #104336

#TimeUsernameProblemLanguageResultExecution timeMemory
104336puyu_liaoNew Home (APIO18_new_home)C++14
100 / 100
2586 ms144260 KiB
#include <bits/stdc++.h> using namespace std; const int INF = (int)1.01e9; void print(vector<int> v) { for (int x : v) printf("%d\n", x); } struct Segtree { int n, N; vector<int> t; Segtree(int _n) { n = _n; N = 1; while (N < n) N <<= 1; t.assign(2 * N, INF); } void upd(int x, int y) { x += N; t[x] = y; while (x > 1) { x >>= 1; t[x] = min(t[x * 2], t[x * 2 + 1]); } } int get(int l, int r) { int ans = INF; l += N; r += N; while (l <= r) { if (l & 1) ans = min(ans, t[l]); if (!(r & 1)) ans = min(ans, t[r]); l = (l + 1) >> 1; r = (r - 1) >> 1; } return ans; } }; struct Shop { int x, type, a, b; }; struct Query { int x, time; }; vector<int> fast(vector<Shop> a, int k, vector<Query> b) { int n = a.size(), m = b.size(); vector<int> ans(m, 0); for (auto &s : a) { s.a = s.a * 3; s.b = s.b * 3 + 2; } for (auto &o : b) o.time = o.time * 3 + 1; sort(a.begin(), a.end(), [&](const Shop &x, const Shop &y) { return x.type < y.type; }); struct Event { int time, type, x; bool operator< (const Event &e) const { return time < e.time; } }; struct Update { int t1, t2, x1, x2, val; }; vector<Update> vct[2]; vct[0].reserve(3 * n + k + 10); vct[1].reserve(3 * n + k + 10); auto addUpdate = [&](int t1, int t2, int l, int r) { if (t1 >= t2) return; int mid = l + (r - l) / 2; vct[0].push_back({ t1, t2, l, mid, l }); vct[1].push_back({ t1, t2, -r, -(r - (r - l) / 2), -r }); }; int ci = 0; for (int c = 0; c < k; c++) { static multiset<pair<int, int>> st; st.clear(); st.insert({ -INF, -1 }); st.insert({ +INF, -1 }); static vector<Event> events; events.clear(); while (ci < n && a[ci].type == c) { auto o = a[ci++]; events.push_back({ o.a, +1, o.x }); events.push_back({ o.b, -1, o.x }); } sort(events.begin(), events.end()); for (auto ev : events) { if (ev.type == +1) { auto it = st.lower_bound({ ev.x, -1 }); int rightX = it->first; int nTime = ev.time; if (rightX == ev.x) nTime = it->second; it--; int leftX = it->first; addUpdate(it->second, ev.time, leftX, rightX); st.erase(it); st.insert({ leftX, ev.time }); st.insert({ ev.x, nTime }); } else { auto it = st.lower_bound({ ev.x, -1 }); int midX = it->first, midT = it->second; st.erase(it); it = st.lower_bound({ ev.x, -1 }); addUpdate(midT, ev.time, midX, it->first); it--; int leftX = it->first; addUpdate(it->second, ev.time, leftX, midX); st.erase(it); st.insert({ leftX, ev.time }); } } assert(st.size() == 2); addUpdate(st.begin()->second, INF, -INF, +INF); } vector<int> perB(m); iota(perB.begin(), perB.end(), 0); sort(perB.begin(), perB.end(), [&](int i, int j) { return b[i].x < b[j].x; }); struct CEvent { int time, type, id; bool operator< (const CEvent &rhs) const { return time < rhs.time; } }; vector<CEvent> events; events.reserve(m + vct[0].size() * 2); for (int i = 0; i < (int)vct[0].size(); i++) { events.push_back({ vct[0][i].t1, 1, i }); events.push_back({ vct[0][i].t2, 2, i }); } for (int i = 0; i < m; i++) events.push_back({ b[i].time, 0, i }); sort(events.begin(), events.end()); Segtree tr(vct[0].size()); for (int ii = 0; ii < 2; ii++) { static vector<pair<int, int>> vv; vv.clear(); for (int i = 0; i < (int)vct[ii].size(); i++) vv.push_back({ vct[ii][i].x2, i }); sort(vv.begin(), vv.end()); vector<int> lb1(vct[ii].size()); for (int i = 0; i < (int)vv.size(); i++) lb1[vv[i].second] = i; vector<int> lb2(m); int ci = 0; for (int i = 0; i < m; i++) { while (ci < (int)vv.size() && vv[ci].first < b[perB[i]].x) ci++; lb2[perB[i]] = ci; } for (auto ev : events) { if (ev.type == 0) { int id = lb2[ev.id]; ans[ev.id] = max(ans[ev.id], b[ev.id].x - tr.get(id, tr.n - 1)); } if (ev.type == 1) { int id = lb1[ev.id]; tr.upd(id, vct[ii][ev.id].x1); } if (ev.type == 2) { int id = lb1[ev.id]; tr.upd(id, INF); } } for (auto &o : b) o.x *= -1; reverse(perB.begin(), perB.end()); } for (int &x : ans) if (x >= INF / 2) x = -1; return ans; } int main() { int n, k, q; scanf("%d%d%d", &n, &k, &q); vector<Shop> a(n); for (int i = 0; i < n; i++) { scanf("%d%d%d%d", &a[i].x, &a[i].type, &a[i].a, &a[i].b); a[i].type--; } vector<Query> b(q); for (int i = 0; i < q; i++) scanf("%d%d", &b[i].x, &b[i].time); print(fast(a, k, b)); }

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &a[i].x, &a[i].type, &a[i].a, &a[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:200:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < q; i++) scanf("%d%d", &b[i].x, &b[i].time);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...