Submission #698632

#	Time	Username	Problem	Language	Result	Execution time	Memory
698632		vjudge1	New Home (APIO18_new_home)	C++17	0 / 100	842 ms	66480 KiB

new_home

#include "bits/stdc++.h"
#define ll long long
using namespace std;
const ll mod = 1000000007;

bool yes[300001];
int ans[300001];

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("cowland.in","r",stdin);
    // freopen("cowland.out","w",stdout);

    int n, k, q;
    cin >> n >> k >> q;
    vector<pair<int, pair<int, int>>> v1;
    vector<pair<pair<int, int>, int>> v2;
    for(int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        v1.push_back({t, {a, b}});
        v2.push_back({{a, 0}, x});
        v2.push_back({{b, q + 10}, x});
    }
    sort(v1.begin(), v1.end());
    vector<pair<int, int>> v3;
    for(int i = 0; i < n; i++) {
        if(!i || v1[i].first != v1[i - 1].first || v1[i].second.first > v1[i - 1].second.second)
            v3.push_back({v1[i].second.first, 0});
        if(i + 1 == n || v1[i].second.second < v1[i + 1].second.first)
            v3.push_back({v1[i].second.second, q + 10});
    }
    for(int i = 0; i < q; i++) {
        int l, y;
        cin >> l >> y;
        v2.push_back({{y, i + 1}, l});
        v3.push_back({y, i + 1});
    }
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());
    int x = 0, sz = v3.size();
    for(int i = 0; i < sz; i++) {
        if(v3[i].second == 0)
            x++;
        else if(v3[i].second == q + 10)
            x--;
        else if(x == k)
            yes[v3[i].second - 1] = 1;
    }
    priority_queue<int> mn, mx;
    sz = v2.size();
    map<int, int> mp1, mp2;
    for(int i = 0; i < sz; i++) {
        // cout << v2[i].first.first << " " << v2[i].first.second << " " << v2[i].second << "\n";
        if(v2[i].first.second == 0) {
            mn.push(-v2[i].second);
            mx.push(v2[i].second);
        }
        else if(v2[i].first.second == q + 10) {
            // cout << mn.top() << " " << mx.top() << " ";
            mp1[v2[i].second]++;
            while(!mn.empty() && mp1[-mn.top()])
                mp1[-mn.top()]--, mn.pop();
            mp2[v2[i].second]++;
            while(!mx.empty() && mp2[mx.top()])
                mp2[mx.top()]--, mx.pop();
            // cout << mn.top() << " " << mx.top() << "\n";
        }
        else if(!mn.empty() && !mx.empty()) {
            // cout << v2[i].second << " " << mn.size() << " " << mx.size() << " " << -mn.top() << " " << mx.top() << "\n";
            ans[v2[i].first.second - 1] = max(abs(v2[i].second + mn.top()), abs(v2[i].second - mx.top()));
        }
    }
    for(int i = 0; i < q; i++) {
        if(yes[i])
            cout << ans[i] << "\n";
        else
            cout << -1 << "\n";
    }

    return 0;
}

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