Submission #1199583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199583		just	New Home (APIO18_new_home)	C++20	12 / 100	5095 ms	63608 KiB

new_home

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

#define int long long
#define vec vector
#define all(x) (x).begin(), (x).end()

using quad = tuple<int, int, int, int>;
using trip = tuple<int, int, int>;

int n, k, q;
vec<vec<trip>> stores;
vec<trip> queries; // { year, location };

signed main() {
    priority_queue<quad, vec<quad>, greater<quad>> to_add, to_rem;
    
    cin >> n >> k >> q;
    stores.resize(k);
    for(int i = n; i--; ) {
        int x, t, a, b; cin >> x >> t >> a >> b;
        t--;
        
        stores[t].emplace_back(x, a, b);
        to_add.push({a, b, x, t});
    }
    
    queries.resize(q);
    int i = 0;
    for(auto &[year, loc, idx]: queries) {
        idx = i;
        i++;
        cin >> loc >> year;
    }
    
    sort(all(queries));
    
    vec<multiset<int>> cur(k);
    
    vec<int> ans(q);
    for(auto [year, loc, idx]: queries) {
        while(to_add.size()) {
            auto [a, b, x, t] = to_add.top();
            if (a > year) break;
            
            cur[t].insert(x);
            to_rem.push({b, a, x, t});
            to_add.pop();
        }
        
        while(to_rem.size()) {
            auto [b, a, x, t] = to_rem.top();
            if (b >= year) break;
            
            cur[t].erase(cur[t].find(x));
            to_rem.pop();
        }
        
        const int inf = LLONG_MAX;
        
        int mx_dist = 0;
        for(int t = 0; t < k; t++) {
            if (cur[t].empty()) mx_dist = inf;
            else {
                int dist = inf;
                
                auto it = cur[t].lower_bound(loc);
                if (it != cur[t].end()) dist = min(dist, abs(*it - loc));
                if (it != cur[t].begin()) {
                    it = prev(it);
                    dist = min(dist, abs(*it - loc));
                }
                
                mx_dist = max(mx_dist, dist);
            }
        }
        
        ans[idx] = mx_dist == LLONG_MAX ? -1 : mx_dist;
    }
    
    for(int x: ans) cout << x << "\n";
}

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