| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 399832 | my99n | 새 집 (APIO18_new_home) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 a = s[type].begin(); a != s[type].end(); a++) {
mn = min(mn, abs(x - a->first));
}
cerr << mn << endl;
auto lb = s[type].lower_bound({x, -1});
if (lb == s[type].end()) lb--;
// cerr << x << ' ' << lb->first << endl;
assert(mn <= abs(x - (lb->first)));
mn = min(mn, abs(x-(a->first)));
if (lb != s[type].begin()) lb--;
assert(mn <= abs(x - (lb->first)));
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] << '\n';
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/