Submission #404875

# Submission time Handle Problem Language Result Execution time Memory
404875 2021-05-15T08:12:11 Z dvdg6566 Road Construction (JOI21_road_construction) C++14
0 / 100
10000 ms 1864160 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;
vector<pair<pi,int>> A;
vpi ans;

struct node{
    ll v;
    node *l,*r;
    node(){
        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;
        }
    }
    void res(){
        v=0;
        if(l)l->res();
        if(r)r->res();
    }
}*root;

struct node2{
    node2 *l,*r;
    set<int> S;
    node2(){
        l=r=nullptr;
    }
    void upd(ll s,ll e,ll x,ll va,ll flag){
        // if(s==-1e9&&e==3e9){
        //     if(flag)cerr<<"ADD ";
        //     else cerr<<"RMV ";
        //     cerr<<x<<' '<<va<<'\n';
        // }
        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){
            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";
    root=new node();
    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;
    }
    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);
    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);
    vi res;
    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';
    }
}
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 30760 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 10176 ms 1864160 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 10156 ms 1214928 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 10156 ms 1214928 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 30760 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 30760 KB Output isn't correct
2 Halted 0 ms 0 KB -