Submission #971567

#	Time	Username	Problem	Language	Result	Execution time	Memory
971567		irmuun	New Home (APIO18_new_home)	C++17	12 / 100	5043 ms	66196 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k,q;
    cin>>n>>k>>q;
    vector<array<ll,3>>v;//-1 open 0 ask 1 close
    ll x[n+5],t[n+5],a[n+5],b[n+5];
    for(ll i=1;i<=n;i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
        v.pb({a[i],-1,i});
        v.pb({b[i],1,i});
    }
    multiset<ll>st[k+5];
    for(ll i=1;i<=k;i++){
        st[i].insert(-1e9);
        st[i].insert(1e9);
    }
    ll l[q+5],y[q+5];
    for(ll i=1;i<=q;i++){
        cin>>l[i]>>y[i];
        v.pb({y[i],0,i});
    }
    sort(all(v));
    ll ans[n+5];
    for(auto [T,y,i]:v){
        if(y==-1){
            st[t[i]].insert(x[i]);
        }
        if(y==0){
            ll mx=0,mn;
            for(ll j=1;j<=k;j++){
                auto it=st[j].lower_bound(l[i]);
                mn=*it-l[i];
                it--;
                mn=min(mn,l[i]-*it);
                mx=max(mx,mn);
            }
            if(mx>=(ll)1e8){
                mx=-1;
            }
            ans[i]=mx;
        }
        if(y==1){
            st[t[i]].erase(st[t[i]].find(x[i]));
        }
    }
    for(ll i=1;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