Submission #1069704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069704		adaawf	New Home (APIO18_new_home)	C++17	0 / 100	1027 ms	77632 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
struct HOME {
    int t, x, y, num, c;
};
bool cmp(HOME aa, HOME bb) {
    if (aa.t == bb.t) return aa.num < bb.num;
    return aa.t < bb.t;
}
long long int a[300005], l[300005], r[300005], mid[300005], res[300005];
long long int t[1200005], d[200005], hh = 0;
map<int, int> mm[300005];
void update(int v, int tl, int tr, int x, long long int y) {
    if (tl == tr) {
        if (t[v] == 0) t[v] = y;
        else t[v] = 0;
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update(v * 2, tl, mid, x, y);
    else update(v * 2 + 1, mid + 1, tr, x, y);
    t[v] = (t[v * 2] ^ t[v * 2 + 1]);
}
long long int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v];
    }
    int mid = (tl + tr) / 2;
    return (sum(v * 2, tl, mid, l, min(r, mid)) ^ sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k, q;
    cin >> n >> k >> q;
    mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 1; i <= k; i++) {
        int h = 1e9;
        a[i] = 1ll * (mt() % h + 1) * (mt() % h + 1);
        hh ^= a[i];
    }
    vector<HOME> v;
    vector<long long int> vv;
    for (int i = 1; i <= n; i++) {
        int u, t, x, y;
        cin >> u >> t >> x >> y;
        vv.push_back(u);
        v.push_back({x, u, t, 1, 0});
        v.push_back({y + 1, u, t, 2, 0});
    }
    for (int i = 1; i <= q; i++) {
        int u, x;
        cin >> u >> x;
        v.push_back({x, u, 0, 3, i});
    }
    sort(v.begin(), v.end(), cmp);
    sort(vv.begin(), vv.end());
    for (auto w : v) {
        if (w.num <= 2) {
            int h = lower_bound(vv.begin(), vv.end(), w.x) - vv.begin() + 1;
            if (w.num == 1) {
                mm[h][w.y]++;
                if (mm[h][w.y] == 1) update(1, 1, n, h, a[w.y]);
            }
            else {
                mm[h][w.y]--;
                if (mm[h][w.y] == 0) update(1, 1, n, h, a[w.y]);
            }
        }
        else {
            int l = 0, r = 1e8, res = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                int h = lower_bound(vv.begin(), vv.end(), w.x - mid) - vv.begin() + 1;
                int k = upper_bound(vv.begin(), vv.end(), w.x + mid) - vv.begin();
                if (sum(1, 1, n, h, k) == hh) {
                    res = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            d[w.c] = res;
        }
    }
    for (int i = 1; i <= q; i++) cout << d[i] << '\n';
}

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