Submission #440172

#	Time	Username	Problem	Language	Result	Execution time	Memory
440172		KULIKOLD	New Home (APIO18_new_home)	C++17	12 / 100	3303 ms	31940 KiB

new_home

//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> super_set;
#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 n,q,k;
int solve(){


    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;
}
vector<int> V[DIM];
super_set S;
int get(int l,int r){
    return S.order_of_key({r,INF})-S.order_of_key({l-1,INF});
}
int solve1(){
    for(int i = 1;i<=n;++i){
        int x,t,a,b;
        cin>>x>>t>>a>>b;
        V[t].push_back(x);
    }
    vector<node> events;
    for(int i = 1;i<=k;++i){
        sort(V[i].begin(),V[i].end());
        for(int j = 0;j<V[i].size();++j){
            int prev = j==0?-INF:V[i][j-1],next = j==V[i].size()-1?INF:V[i][j+1];
            int l = max(0,(V[i][j]+prev)/2);
            int r = min(int(1E9),(V[i][j]+next)/2);
            events.push_back({l,V[i][j],i,0});
            events.push_back({r,V[i][j],-i,0});
        }
    }
    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 l = 0,r = 1E9;
            while(l!=r){
                int tm = (l+r)/2;
                if (get(to.x-tm,to.x+tm)==k)
                    r = tm;
                else l = tm+1;
            }
            if (l==1E9)
                ans[to.pos] = -1;
            else ans[to.pos] = l;
        }
        else{
            if (to.type<0)
                S.erase({to.x,-to.type});
            else S.insert({to.x,to.type});
        }
    }
    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);
    cin>>n>>k>>q;
    if (k<=400)
        solve();
    else
    solve1();
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int solve1()':
new_home.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int j = 0;j<V[i].size();++j){
      |                       ~^~~~~~~~~~~~
new_home.cpp:85:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             int prev = j==0?-INF:V[i][j-1],next = j==V[i].size()-1?INF:V[i][j+1];
      |                                                   ~^~~~~~~~~~~~~~~

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