Submission #260859

#	Time	Username	Problem	Language	Result	Execution time	Memory
260859		wiwiho	New Home (APIO18_new_home)	C++14	5 / 100	5116 ms	1048576 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;
     
        vector<map<int, vector<pii>>> e(k + 1);
        for(int i = 0; i < n; i++){
            int x, t, a, b;
            cin >> x >> t >> a >> b;
            e[t][a].eb(mp(-1, x));
            e[t][b + 1].eb(mp(-2, x));
        }
     
        for(int i = 0; i < q; i++){
            int l, y;
            cin >> l >> y;
            for(int j = 1; j <= k; j++) e[j][y].eb(mp(i, l));
        }
     
        vector<int> ans(q);
     
        for(int t = 1; t <= k; t++){
     
            multiset<int> st;
            for(auto& j : e[t]){
                for(pii i : j.S){
                    if(i.F == -1) st.insert(i.S);
                    else if(i.F == -2) st.erase(st.find(i.S));
                    else{
                        int id = i.F, l = i.S;
                        auto it = st.lower_bound(l);
                        int dis = MAX;
                        if(it != st.end()) dis = min(dis, *it - l);
                        if(it != st.begin()) dis = min(dis, l - *prev(it));
                        //cerr << id << " " << t << " " << dis << "\n";
                        ans[id] = max(ans[id], dis);
                    }
                }
            }
     
        }
     
        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: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20