Submission #399751

#TimeUsernameProblemLanguageResultExecution timeMemory
399751my99nNew Home (APIO18_new_home)C++17
0 / 100
1 ms460 KiB
#include<bits/stdc++.h> using namespace std; struct event { int et, x, t, y, i; bool operator < (const event & o) const { if (y == o.y) return et < o.et; // open query close return y < o.y; } }; vector<event> e; set<pair<int,int>> s[500]; int ans[100100]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k, q; cin >> n >> k >> q; assert(k < 500); for (int i = 1; i <= n; i++) { int x, t, a, b; cin >> x >> t >> a >> b; e.push_back({1, x, t, a, i}); e.push_back({3, x, t, b, i}); } for (int i = 1; i <= q; i++) { int l, y; cin >> l >> y; e.push_back({2, l, 0, y, i}); } sort(e.begin(), e.end()); for (auto [et, x, t, y, i] : e) { if (et == 1) s[t].insert({x, i}); if (et == 3) s[t].erase({x, i}); if (et == 2) { for (int type = 1; type <= k; type++) { if (s[type].empty()) { ans[i] = -1; break; } int mn = 1e9; for (auto [loc, ind] : s[type]) { mn = min(mn, abs(x - loc)); } auto a = s[type].lower_bound({x, -1}); mn = min(mn, abs(x-(a->first))); if (a != s[type].end()) mn = min(mn, abs(x-(next(a)->first))); if (a != s[type].begin()) mn = min(mn, abs(x-(prev(a)->first))); ans[i] = max(ans[i], mn); } } } for (int i = 1; i <= q; i++) cout << ans[i] << endl; 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...