Submission #404885

#	Time	Username	Problem	Language	Result	Execution time	Memory
404885		dvdg6566	Road Construction (JOI21_road_construction)	C++14	0 / 100	10107 ms	120536 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define f first 
#define s second
#define mp make_pair
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
 
const ll MAXN=250100;
const ll MAXK=19;

ll N,K,a,b;
vpi V;
vi res;
vector<pair<pi,int>> A;
vpi ans;
ll W,M;

struct node{
    ll v;
    node *l,*r;
    node(){
        v=0;
        l=r=nullptr;
    }
    void upd(ll s,ll e,ll x,ll va){
        // if(s==-1e9&&e==3e9){
        //     cerr<<"Upd "<<x<<' '<<va<<'\n';
        // }
        if(s==e){
            // cerr<<"Upd "<<x<<' '<<va<<'\n';
            v+=va;return;
        }
        ll m=(ll)(s+e+2e9)/2-1e9;
        // cerr<<s<<' '<<m<<' '<<e<<'\n';
        if(x<=m){
            if(!l)l=new node();
            l->upd(s,m,x,va);
        }
        else{
            if(!r)r=new node();
            r->upd(m+1,e,x,va);
        }
        v=0;
        if(l)v+=l->v;
        if(r)v+=r->v;
    }
    ll query(ll s,ll e,ll x,ll y){
        ll m=(ll)(2e9+s+e)/2-1e9;
        if(s==x&&e==y){
            return v;
        }
        if(y<=m){
            if(!l)return 0;
            return l->query(s,m,x,y);
        }else if(x>m){
            if(!r)return 0;
            return r->query(m+1,e,x,y);
        }else{
            ll ans=0;
            if(l)ans+=l->query(s,m,x,m);
            if(r)ans+=r->query(m+1,e,m+1,y);
            return ans;
        }
    }
}*root;

struct node2{
    node2 *l,*r;
    set<int> S;
    node2(){
        l=r=nullptr;
        S.clear();
    }
    void upd(ll s,ll e,ll x,ll va,ll flag){
        ++W;
        if(flag)S.insert(va);
        else S.erase(va);
        if(s==e)return;
       
        ll m=(ll)(s+e+2e9)/2-1e9;
        if(x<=m){
            if(!l)l=new node2();
            l->upd(s,m,x,va,flag);
        }
        else{
            if(!r)r=new node2();
            r->upd(m+1,e,x,va,flag);
        }
    }
    void query(ll s,ll e,ll x,ll y,ll k){
        ll m=(ll)(2e9+s+e)/2-1e9;
        if(s==x&&e==y){
            M+=SZ(S);
            if(M>K)assert(0);
            // if(SZ(S))cerr<<SZ(S)<<'\n';
            for(auto i:S){
                if(k<i){
                    ans.pb(k,i);
                }
            }
            return;
        }
        if(y<=m){
            if(!l)return;
            return l->query(s,m,x,y,k);
        }else if(x>m){
            if(!r)return;
            return r->query(m+1,e,x,y,k);
        }else{
            if(l)l->query(s,m,x,m,k);
            if(r)r->query(m+1,e,m+1,y,k);
        }
    }
}*root2;

ll cnt(ll d){
    // cerr<<"HI\n";
    ll s=-1;
    ll e=-1;
    ll ans=0;
    for(auto i:A){
        ll ep=i.f.f+d;
        ll sp=i.f.f-d;
        while(e+1<N&&A[e+1].f.f<=ep){++e;root->upd(-1e9,(ll)3e9,A[e].f.s,1);}
        while(s+1<N&&A[s+1].f.f<sp){++s;root->upd(-1e9,(ll)3e9,A[s].f.s,-1);}
        ll t=root->query(-1e9,(ll)3e9,i.f.s-d,i.f.s+d);
        ans+=t;
    }
    while(s+1<N){++s;root->upd(-1e9,(ll)3e9,A[s].f.s,-1);}
    return (ans-N)/2;
}

void generate(ll d){
    ll s=-1;
    ll e=-1;
    for(auto i:A){
        ll ep=i.f.f+d;
        ll sp=i.f.f-d;
        while(e+1<N&&A[e+1].f.f<=ep){++e;root2->upd(-1e9,(ll)3e9,A[e].f.s,A[e].s,1);}
        while(s+1<N&&A[s+1].f.f<sp){++s;root2->upd(-1e9,(ll)3e9,A[s].f.s,A[s].s,0);}
        root2->query(-1e9,(ll)3e9,i.f.s-d,i.f.s+d,i.s);
    }
}

ll d(int a,int b){
    return abs(V[a].f-V[b].f) + abs(V[a].s-V[b].s);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    root=new node();
    root2=new node2();
    cin>>N>>K;
    for(ll i=0;i<N;++i){
        cin>>a>>b;
        V.pb(a,b);
        A.pb(mp(b-a,b+a),i);
    }
    sort(ALL(A));
    ll l=0;
    ll u=2e9;
    while(u-l>0){
        ll m=(l+u)/2;
        ll k=cnt(m);
        if(k>=K)u=m;
        else l=m+1;
    }
    assert(SZ(ans)<K);
    --l;
    generate(l);
    // cout<<W<<' '<<M<<'\n';
    for(auto i:ans){
        res.pb(d(i.f,i.s));
    }
    sort(ALL(res));
    while(SZ(res)<K)res.pb(l+1);
    for(auto i:res){
        cout<<i<<'\n';
    }
}

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