Submission #1167035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167035		thdh__	New Home (APIO18_new_home)	C++20	12 / 100	5087 ms	48168 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

// We'll store: (time, eventType, XorL, TorIdx)
// eventType: 0 = open store, 1 = close store, 2 = query
// For store open/close: XorL = store location, TorIdx = store type
// For query: XorL = l (the user location), TorIdx = index of this query
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // We'll collect all events in one vector
    vector<array<long long,4>> events;
    events.reserve(n*2 + q);

    // Read the store data
    //   store i: (x, t, a, b) => open at time a, close at time b+1
    for(int i=0; i<n; i++){
        long long x, t, a, b;
        cin >> x >> t >> a >> b;
        t--; // make store type zero-based
        // open at time = a
        events.push_back({a, 0, x, t});
        // close at time = b+1
        events.push_back({b+1, 1, x, t});
    }

    // We'll store answers for queries
    vector<long long> ans(q);

    // Read queries
    //   query i: (l, y)
    for(int i=0; i<q; i++){
        long long l, y;
        cin >> l >> y;
        // event: time=y, eventType=2, XorL=l, TorIdx=i (query index)
        events.push_back({y, 2, l, i});
    }

    // Sort events primarily by time, secondarily by eventType
    // so open (0) happens before close (1) before query (2) if times tie
    sort(events.begin(), events.end(),
         [](auto &A, auto &B){
             if (A[0] != B[0]) return A[0] < B[0];
             return A[1] < B[1];
         });

    // We maintain k multisets, one for each type
    vector< multiset<long long> > storeLocs(k);
    // openCount[t] = how many stores of type t are currently open
    vector<int> openCount(k, 0);
    // how many distinct types have at least 1 open store
    int openTypes = 0;

    // Process in ascending time
    for (auto &e : events) {
        long long time = e[0];
        int evType     = (int)e[1];
        long long xOrL = e[2];
        int tOrIdx     = (int)e[3];

        if (evType == 0) {
            // open store
            int t = tOrIdx; 
            storeLocs[t].insert(xOrL);
            if (openCount[t] == 0) {
                openTypes++;
            }
            openCount[t]++;
        }
        else if (evType == 1) {
            // close store
            int t = tOrIdx;
            auto it = storeLocs[t].find(xOrL);
            if (it != storeLocs[t].end()) {
                storeLocs[t].erase(it);
                openCount[t]--;
                if (openCount[t] == 0) {
                    openTypes--;
                }
            }
        }
        else {
            // query
            int qIdx = tOrIdx; // which query index this is
            if (openTypes < k) {
                // not all types have an open store
                ans[qIdx] = -1;
            } else {
                long long l = xOrL;
                // We must compute the "inconvenience index" = 
                //   max_{t in [0..k-1]} distance( l, nearest store of type t )
                // We'll do it by scanning all types.
                long long worstDist = 0;
                for(int t=0; t<k; t++){
                    // storeLocs[t] is non-empty
                    // find the nearest store to l
                    //   that is either the lower_bound(l) or the one just before it
                    auto it = storeLocs[t].lower_bound(l);
                    long long distHere = LLONG_MAX;
                    if (it != storeLocs[t].end()) {
                        distHere = min(distHere, llabs(*it - l));
                    }
                    if (it != storeLocs[t].begin()) {
                        auto pit = prev(it);
                        distHere = min(distHere, llabs(*pit - l));
                    }
                    worstDist = max(worstDist, distHere);
                }
                ans[qIdx] = worstDist;
            }
        }
    }

    // Output results
    for (auto &val : ans) {
        cout << val << "\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