Submission #980592

#	Time	Username	Problem	Language	Result	Execution time	Memory
980592		Unforgettablepl	New Home (APIO18_new_home)	C++17	12 / 100	5028 ms	117116 KiB

new_home

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

#define int long long

int ans[300001];
map<int,vector<tuple<int,int,int>>> queries;
multiset<int> curr[300001];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k,q;
    cin >> n >> k >> q;
    for(int i=1;i<=n;i++){
        int x,t,a,b;cin>>x>>t>>a>>b;
        queries[a].emplace_back(1,x,t);
        queries[b+1].emplace_back(0,x,t);
    }
    for(int i=1;i<=q;i++){
        int l,y;cin>>l>>y;
        queries[y].emplace_back(2,l,i);
    }
    for(int i=1;i<=k;i++)curr[i].insert(1e9);
    for(int i=1;i<=k;i++)curr[i].insert(-1e9);
    for(auto&[tim,vec]:queries){
        for(auto&[type,loc,idx]:vec){
            if(type==0){
                curr[idx].erase(curr[idx].find(loc));
            } else if(type==1){
                curr[idx].insert(loc);
            } else {
                for(int i=1;i<=k;i++){
                    auto iter = curr[i].lower_bound(loc);
                    int myans = *iter-loc;
                    iter--;
                    myans = min(myans,loc-*iter);
                    ans[idx] = max(ans[idx],myans);
                }
            }
        }
    }
    for(int i=1;i<=q;i++)cout<<(ans[i]>1e8 ? -1 : ans[i])<<'\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