Submission #160548

#	Time	Username	Problem	Language	Result	Execution time	Memory
160548		Minnakhmetov	New Home (APIO18_new_home)	C++14	12 / 100	5102 ms	57776 KiB

new_home

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

struct E {
    int p, t, x, y;
};

const int N = 3e5 + 5, INF = 1e9;
vector<E> v;
int ans[N], mn[N];
multiset<int> st[N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, k, q;
    cin >> n >> k >> q;

    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        t--;
        v.push_back({a, 0, x, t});
        v.push_back({b + 1, 1, x, t});
    }

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back({y, 2, x, i});
    }

    sort(all(v), [](const E &a, const E &b) {
        return a.p == b.p ? a.t < b.t : a.p < b.p;
    });

    for (E e : v) {
        if (e.t == 0) {
            st[e.y].insert(e.x);
        }
        else if (e.t == 1) {
            st[e.y].erase(st[e.y].find(e.x));
        }
        else {
            fill(mn, mn + k, INF);
            for (int i = 0; i < k; i++) {
                auto it = st[i].lower_bound(e.x);
                if (it != st[i].end())
                    mn[i] = min(mn[i], *it - e.x);
                if (it != st[i].begin()) {
                    it--;
                    mn[i] = min(mn[i], e.x - *it);
                }
            }
            int cur = *max_element(mn, mn + k);
            ans[e.y] = (cur == INF ? -1 : cur);
        }
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

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