Submission #1028474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028474		vjudge1	New Home (APIO18_new_home)	C++17	12 / 100	1995 ms	237388 KiB

new_home

#include<bits/stdc++.h>
using namespace std;
map<int,vector<pair<int,int>>> ad,del,qr;
int ans[100100];
multiset<int>stor[401];
set<int>stuffhappens;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,k,q;
    cin>>n>>k>>q;
    for(int i=0;i<n;i++){
        int l,r,a,b;
        cin>>a>>b>>l>>r;
        ad[l].push_back({a,b});
        del[r+1].push_back({a,b});
        stuffhappens.insert(l);
        stuffhappens.insert(r+1);
    }
    for(int i=0;i<q;i++){
        int x,y; cin>>x>>y;
        qr[y].push_back({x,i});
        stuffhappens.insert(y);
    }
    for(auto year:stuffhappens){
        for(auto[p,t]:ad[year])
            stor[t].insert(p);
        for(auto[p,t]:del[year])
            stor[t].erase(stor[t].find(p));
        for(auto[p,i]:qr[year]) {
            int mx=0;
            for(int t=1;t<=k;t++){
                if(stor[t].empty()){
                    mx=-1;break;
                }
                int TIS=1e9;
                auto it=stor[t].lower_bound(p);
                if(it!=stor[t].end())TIS=*it-p;
                if(it!=stor[t].begin())
                    TIS=min(TIS,p-*--it);
                mx=max(mx,TIS);
            }
            ans[i]=mx;
        }
    }
    for(int i=0;i<q;i++)
        cout<<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