Submission #849169

#TimeUsernameProblemLanguageResultExecution timeMemory
849169hngwlogNew Home (APIO18_new_home)C++14
12 / 100
1513 ms9944 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define _size(x) (int)x.size() #define BIT(i, x) ((x >> i) & 1) #define MASK(n) ((1 << n) - 1) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++) #define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--) #define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i) #define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i) #define FORALL(i, a) for (auto i: a) #define fastio ios_base::sync_with_stdio(0); cin.tie(0); struct storeNode { int x, t, a, b; }; struct queryNode { int l, y, id; }; int n, k, q; vector<storeNode> store; vector<queryNode> qu; namespace subtask12 { const int inf = 1e9; void main() { vector<pair<int, int>> g; FOR(i, 1, n) g.push_back({store[i].a, i}), g.push_back({store[i].b, - i}); REP(i, q) g.push_back({qu[i].y, 0}); sort(g.begin(), g.end(), [&] (const pair<int, int> a, pair<int, int> b) { return a.fi != b.fi ? a.fi < b.fi : a.se > b.se; }); sort(qu.begin(), qu.end(), [&] (const queryNode a, queryNode b) { return a.y < b.y; }); vector<int> ans(q); vector<multiset<int>> mts(k + 1); int i = 0, z = 0; while (i < _size(g)) { int j = i; while (j < _size(g) && g[j].fi == g[i].fi && g[j].se > 0) { int id = g[j].se; mts[store[id].t].insert(store[id].x); j++; } while (j < _size(g) && g[j].fi == g[i].fi && g[j].se == 0) j++; while (z < q && qu[z].y == g[i].fi) { int res = - 1; FOR(id, 1, k) { if (mts[id].empty()) { res = - 1; break; } auto it = mts[id].lower_bound(qu[z].l); int _res = inf; if (it != mts[id].end()) _res = min(_res, *it - qu[z].l); if (it != mts[id].begin()) { --it; _res = min(_res, qu[z].l - *it); } res = max(res, _res); } ans[qu[z].id] = res; z++; } while (j < _size(g) && g[j].fi == g[i].fi) { int id = - g[j].se; mts[store[id].t].erase(mts[store[id].t].find(store[id].x)); j++; } i = j; } REP(i, q) cout << ans[i] << '\n'; } } int main() { fastio; cin >> n >> k >> q; store.resize(n + 1); FOR(i, 1, n) { int x, t, a, b; cin >> x >> t >> a >> b; store[i] = {x, t, a, b}; } qu.resize(q); REP(i, q) { cin >> qu[i].l >> qu[i].y; qu[i].id = i; } if (max(n, q) <= 60000 && k <= 400) subtask12::main(); return 0; }
#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...