Submission #260862

#	Time	Username	Problem	Language	Result	Execution time	Memory
260862		wiwiho	New Home (APIO18_new_home)	C++14	12 / 100	5086 ms	90448 KiB

new_home

#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int, int>

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    map<int, vector<pair<int, pii>>> e;
    for(int i = 0; i < n; i++){
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        e[a].eb(mp(1, mp(x, t)));
        e[b + 1].eb(mp(-1, mp(x, t)));
    }

    for(int i = 0; i < q; i++){
        int l, y;
        cin >> l >> y;
        e[y].eb(mp(0, mp(l, i)));
    }

    vector<int> ans(q);

    vector<multiset<int>> p(k + 1);

    for(auto& i : e){
        for(auto j : i.S){
            if(j.F == 1) p[j.S.S].insert(j.S.F);
            else if(j.F == -1) p[j.S.S].erase(p[j.S.S].find(j.S.F));
            else{

                for(int t = 1;  t <= k; t++){
                    int tmp = MAX;
                    auto it = p[t].lower_bound(j.S.F);
                    if(it != p[t].end()) tmp = min(tmp, *it - j.S.F);
                    if(it != p[t].begin()) tmp = min(tmp, j.S.F - *prev(it));
                    ans[j.S.S] = max(ans[j.S.S], tmp);
                }

            }
        }
    }

    for(int i = 0; i < q; i++){
        if(ans[i] == MAX) cout << "-1\n";
        else 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