Submission #440152

#	Time	Username	Problem	Language	Result	Execution time	Memory
440152		KULIKOLD	New Home (APIO18_new_home)	C++17	12 / 100	3684 ms	35884 KiB

new_home

//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int DIM = 3E5+7;
const int SZ = 407;
const int INF = 1E9+7;
set<pair<int,int> > K[SZ];
struct node{
    int t,x,type,pos;
};
bool mc(node &a,node &b){
    if (a.t==b.t)
        return (a.type==0)<(b.type==0);
    return a.t<b.t;
}
int ans[DIM];
int solve(){
    int n,q,k;
    cin>>n>>k>>q;
    vector<node> events;
    for(int i = 1;i<=n;++i){
        int x,t,l,r;
        cin>>x>>t>>l>>r;
        events.push_back({l,x,t,i});
        events.push_back({r+1,x,t,-i});
    }
    for(int i = 1;i<=q;++i){
        int x,t;
        cin>>x>>t;
        events.push_back({t,x,0,i});
    }
    sort(events.begin(),events.end(),mc);
    for(auto to:events){
        if (to.type==0){
            int dist = 0;
            for(int i = 1;i<=k;++i){
                int d = INF;
                auto lb = K[i].lower_bound({to.x,INF});
                if (lb!=K[i].begin()){
                    lb = prev(lb);
                    d = min(d,to.x-lb->first);
                }
                auto rb = K[i].lower_bound({to.x,0});
                if (rb!=K[i].end()){
                    d = min(d,rb->first-to.x);
                }
                dist = max(dist,d);
            }
            if (dist==INF)
                ans[to.pos] = -1;
            else ans[to.pos] = dist;
        }
        else{
            if (to.pos<0)
                K[to.type].erase({to.x,-to.pos});
            else K[to.type].insert({to.x,to.pos});
        }
    }
    for(int i = 1;i<=q;++i)
        cout<<ans[i]<<endl;
    return 1;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    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