oj.uz

Submission #404924

# Submission time Handle Problem Language Result Execution time Memory
404924 2021-05-15T10:08:39 Z dvdg6566 Road Construction (JOI21_road_construction) C++14
32 / 100
 10000 ms 2097156 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)/2;
        // 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)(s+e)/2;
        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)/2;
        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)(s+e)/2;
        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;
    root=new node();
    // 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)0,(ll)10e9,(ll)5e9+A[e].f.s,1);
        }
        while(s+1<N&&A[s+1].f.f<sp){
            ++s;
            root->upd((ll)0,(ll)10e9,(ll)5e9+A[s].f.s,-1);
        }
        ll t=root->query((ll)0,(ll)10e9,i.f.s-d+5e9,i.f.s+d+5e9);
        // cerr<<s<<' '<<e<<' '<<t<<'\n';
        ans+=t;
    }
    // while(s+1<N){++s;root->upd((ll)0,(ll)10e9,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((ll)0,(ll)10e9,5e9+A[e].f.s,A[e].s,1);}
        while(s+1<N&&A[s+1].f.f<sp){++s;root2->upd((ll)0,(ll)10e9,5e9+A[s].f.s,A[s].s,0);}
        root2->query((ll)0,(ll)10e9,5e9+i.f.s-d,i.f.s+d+5e9,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);
    }

    sort(ALL(A));
    ll l=0;
    ll u=4e9;
    while(u-l>0){
        ll m=(l+u)/2;
        ll k=cnt(m);
        if(k>=K)u=m;
        else l=m+1;
    }

    --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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 36928 KB Output is correct
2 Correct 124 ms 36924 KB Output is correct
3 Correct 95 ms 29856 KB Output is correct
4 Correct 90 ms 29504 KB Output is correct
5 Correct 98 ms 23824 KB Output is correct
6 Correct 23 ms 1392 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 6589 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10191 ms 1639944 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 10191 ms 1639944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 36928 KB Output is correct
2 Correct 124 ms 36924 KB Output is correct
3 Correct 95 ms 29856 KB Output is correct
4 Correct 90 ms 29504 KB Output is correct
5 Correct 98 ms 23824 KB Output is correct
6 Correct 23 ms 1392 KB Output is correct
7 Correct 9067 ms 1765864 KB Output is correct
8 Correct 9516 ms 1765124 KB Output is correct
9 Correct 94 ms 29556 KB Output is correct
10 Correct 7847 ms 1578504 KB Output is correct
11 Correct 6547 ms 1446360 KB Output is correct
12 Correct 2884 ms 21420 KB Output is correct
13 Correct 2917 ms 25956 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 36928 KB Output is correct
2 Correct 124 ms 36924 KB Output is correct
3 Correct 95 ms 29856 KB Output is correct
4 Correct 90 ms 29504 KB Output is correct
5 Correct 98 ms 23824 KB Output is correct
6 Correct 23 ms 1392 KB Output is correct
7 Runtime error 6589 ms 2097156 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -