Submission #261006

#	Time	Username	Problem	Language	Result	Execution time	Memory
261006		emanIaicepsa	New Home (APIO18_new_home)	C++14	0 / 100	344 ms	47224 KiB

new_home

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<int>
#define pb emplace_back
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
#define mem(n,m) memset(n,m,sizeof(n))
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){cerr<<x<<'\n';}
template<typename A,typename ...B> void _do(A x,B ...y){cerr<<x<<", ";_do(y...);}

int n,k,q;

struct shop{
    int x,t,a,b;
}arr[300005];

struct query{
    int x,t,id;
    bool operator<(const query &b){
        return t<b.t;
    }
}que[300005];

deque<pii> in, out;

multiset<ll> s[405];

void add(ll x){
    int type = arr[x].t, pos = arr[x].x;
    s[type].insert(pos);
}

void sub(ll x){
    int type = arr[x].t, pos = arr[x].x;
    s[type].erase(s[type].find(pos));
}

ll Query(ll k,ll pos){
    if(s[k].empty()) return 1e15;
    auto iter = s[k].lower_bound(pos);
    ll ans = 1e15;
    if(iter != s[k].end()) ans = min(ans, *iter - pos);
    if(iter != s[k].begin()){
        iter--;
        ans = min(ans, pos - *iter);
    }
    return ans;
}

ll ans[300005];

signed main(){
	IOS;
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i].x>>arr[i].t>>arr[i].a>>arr[i].b;
        in.pb(arr[i].a, i);
        out.pb(arr[i].b+1, i);
    }

    sort(all(in)); sort(all(out));
    for(int i=1;i<=q;i++){
        cin>>que[i].x>>que[i].t;
        que[i].id = i;
    }

    sort(que+1,que+1+n);

    for(int i=1;i<=q;i++){
        //dbg(i);
        while(!in.empty() && in[0].fi <= que[i].t ){
            add(in[0].se);
            //dbg(in[0].se);
            in.pop_front();
        }
        while(!out.empty() && out[0].fi <= que[i].t){
            sub(out[0].se);
            //dbg(out[0].se);
            out.pop_front();
        }
        ll ta = 0;
        for(int j=1;j<=k;j++){
            ta = max(ta, Query(j,que[i].x));
        }
        if(ta > 1e10) ta = -1;
        ans[que[i].id] = ta;
    }

    for(int i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }

}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

1 1 1
100000000 1 1 1
1 1
*/

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