oj.uz

Submission #404911

# Submission time Handle Problem Language Result Execution time Memory
404911 2021-05-15T09:50:34 Z dvdg6566 Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 126484 KB 
#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,ll>> 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==e){
            // cerr<<"Upd "<<x<<' '<<va<<'\n';
            v+=va;return;
        }
        ll m=(ll)(s+e+4e9)/2-2e9;
        // 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)(4e9+s+e)/2-2e9;
        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<ll> S;
    node2(){
        l=r=nullptr;
        S.clear();
    }
    void upd(ll s,ll e,ll x,ll va,ll flag){
        ++W;
        if(flag==1)S.insert(va);
        else S.erase(va);
        if(s==e)return;
        
        ll m=(ll)(s+e+4e9)/2-2e9;
        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)(4e9+s+e)/2-2e9;
        if(s==x&&e==y){
            // if(SZ(S))cerr<<SZ(S)<<'\n';
            for(auto i:S){
                if(i<k){
                    ans.pb(k,i);
                }else break;
            }
            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){
    if(d<0)return 0;
    // 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((ll)-2e9,(ll)3e9,A[e].f.s,1);}
        while(s+1<N&&A[s+1].f.f<sp){++s;root->upd((ll)-2e9,(ll)3e9,A[s].f.s,-1);}
        ll t=root->query((ll)-2e9,(ll)3e9,i.f.s-d,i.f.s+d);
        // cerr<<sp<<' '<<ep<<'\n';
        ans+=t;
    }
    while(s+1<N){++s;root->upd((ll)-2e9,(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(-2e9,(ll)3e9,A[e].f.s,A[e].s,1);}
        while(s+1<N&&A[s+1].f.f<sp){++s;root2->upd(-2e9,(ll)3e9,A[s].f.s,A[s].s,0);}
        root2->query(-2e9,(ll)3e9,i.f.s-d,i.f.s+d,i.s);
    }
}

ll d(ll a,ll 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);
    }
    // cnt(2e9);
    // return 0;
    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;
    }
    // cerr<<l<<'\n';

    --l;
    generate(l);
    // cout<<W<<' '<<M<<'\n';
    for(auto i:ans){
        res.pb(d(i.f,i.s));
    }
    // assert(SZ(res)<K);
    sort(ALL(res));
    while(SZ(res)<K)res.pb(l+1);
    // assert(SZ(res)==K);
    // cerr<<SZ(res)<<'\n';
    for(auto i:res){
        cout<<i<<'\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 14632 KB Output is correct
2 Correct 128 ms 14732 KB Output is correct
3 Incorrect 98 ms 13120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10028 ms 120872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10097 ms 126484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10097 ms 126484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 14632 KB Output is correct
2 Correct 128 ms 14732 KB Output is correct
3 Incorrect 98 ms 13120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 14632 KB Output is correct
2 Correct 128 ms 14732 KB Output is correct
3 Incorrect 98 ms 13120 KB Output isn't correct
4 Halted 0 ms 0 KB -