Submission #546753

#	Time	Username	Problem	Language	Result	Execution time	Memory
546753		Monarchuwu	New Home (APIO18_new_home)	C++17	12 / 100	5102 ms	57516 KiB

new_home

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;

const int N = 3e5 + 7, inf = 1e9 + 7;
int n, k, q, cnt;
struct Data {
    int x, type, time, op;
    Data() {}
    Data(int x, int type, int time, int op) : x(x), type(type), time(time), op(op) {}
    bool operator < (const Data &o) const {
        if (time != o.time) return time < o.time;
        return op > o.op;
    }
} a[N * 3];

multiset<int> s[N];
int ans[N];
void solve() {
    for (int i = 1, id; i <= cnt; ++i) {
        id = a[i].type;
        if (a[i].op == 1)
            s[id].insert(a[i].x);
        else if (a[i].op == -1)
            s[id].erase(s[id].find(a[i].x));
        else {
            for (int j = 1; j <= k; ++j) {
                if (s[j].empty()) { ans[id] = -1; break; }

                int dist(inf);
                multiset<int>::iterator it = s[j].lower_bound(a[i].x);
                if (it != s[j].end()) dist = min(dist, *it - a[i].x);
                if (it != s[j].begin()) dist = min(dist, a[i].x - *(--it));
                ans[id] = max(ans[id], dist);
            }
        }
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> k >> q;
    for (int i = 0, x, t, l, r; i < n; ++i) {
        cin >> x >> t >> l >> r;
        a[++cnt] = Data(x, t, l, 1);
        a[++cnt] = Data(x, t, r, -1);
    }
    for (int i = 0; i < q; ++i) {
        int l, y; cin >> l >> y;
        a[++cnt] = Data(l, i, y, 0);
    }

    sort(a + 1, a + cnt + 1);
    solve();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20