Submission #995556

#	Time	Username	Problem	Language	Result	Execution time	Memory
995556		snpmrnhlol	Road Construction (JOI21_road_construction)	C++17	100 / 100	3420 ms	23128 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 25e4;
const ll inf = 1e18;
mt19937 rng;
struct treap{
    ll l,r;
    ll x,y;
    ll val;
}v[N + 1];
struct point{
    ll x,y;
}v2[N];
ll cnt = 1;
ll lid,rid;
ll n,k,cnt2 = 0;
ll ans[N + 1];
void dbgtreap(ll pos){
    cout<<pos<<' '<<v[pos].l<<' '<<v[pos].r<<' '<<v[pos].x<<' '<<v[pos].y<<' '<<v[pos].val<<'\n';
    if(v[pos].l != 0)dbgtreap(v[pos].l);
    if(v[pos].r != 0)dbgtreap(v[pos].r);
}
ll mergetreap(ll l, ll r){
    if(l == 0){return r;}
    if(r == 0){return l;}
    if(v[l].y <= v[r].y){
        v[r].l = mergetreap(l, v[r].l);
        return r;
    }else{
        v[l].r = mergetreap(v[l].r, r);
        return l;
    }
}
void splittreap(ll node, ll nr, ll nr2){
    if(node == 0){
        lid = 0;
        rid = 0;
        return;
    }
    if(v[node].x < nr || (v[node].x == nr && v[node].val <= nr2)){
        splittreap(v[node].r, nr, nr2);
        v[node].r = lid;
        lid = node;
    }else{
        splittreap(v[node].l, nr, nr2);
        v[node].l = rid;
        rid = node;
    }
}
ll ins(ll p, ll x, ll y, ll val){
    if(p == 0){
        v[cnt] = {0,0,x,y,val};
        cnt++;
        return cnt - 1;
    }
    splittreap(p, x, val);
    v[cnt] = {0,0,x,y,val};
    p = mergetreap(lid, cnt);
    p = mergetreap(p, rid);
    cnt++;
    return p;
}
ll del(ll p, ll x, ll val){
    splittreap(p, x, val - 1);
    ll leftside = lid;
    ll rightside = rid;
    splittreap(rid, x, val);
    ll id = mergetreap(leftside, rid);
    return id;
}
void add(ll pt,ll x,ll y){
    if(pt == 0)return;
    if(cnt2 > k)return;
    ans[cnt2++] = max(abs(v[pt].x - y),abs(v[pt].val - x));
    add(v[pt].l,x,y);
    add(v[pt].r,x,y);
}
ll get(ll x){
    cnt = 1;
    cnt2 = 0;
    ll treapid = 0;
    ll pt = 0;
    for(ll i = 0;i < n;i++){
        while(pt < i && v2[pt].x < v2[i].x - x){
            treapid = del(treapid,v2[pt].y,v2[pt].x);
            pt++;
        }
        splittreap(treapid,v2[i].y - x,-inf);
        ll p1 = lid;
        splittreap(rid,v2[i].y + x + 1,-inf);
        ll p2 = lid;
        ll p3 = rid;
        //dbgtreap(p2);
        //cout<<"p2 "<<p2<<' '<<i<<' '<<x<<' '<<v2[i].x<<' '<<v2[i].y<<'\n';
        add(p2,v2[i].x,v2[i].y);
        treapid = mergetreap(p1,p2);
        treapid = mergetreap(treapid,p3);
        treapid = ins(treapid,v2[i].y,rand()%69420,v2[i].x);
        if(cnt2 > k)return cnt2;
    }
    return cnt2;
}
int main(){
    cin>>n>>k;
    for(ll i = 0;i < n;i++){
        cin>>v2[i].x>>v2[i].y;
        v2[i] = {v2[i].x + v2[i].y,v2[i].x - v2[i].y};
    }
    sort(v2,v2 + n,[&](point a,point b){
         return a.x < b.x;
    });
    ll l = 0,r = inf;
    while(l != r){
        ll mij = (l + r)/2;
        if(get(mij) <= k){
            l = mij + 1;
        }else r = mij;
    }
    get(l - 1);
    sort(ans,ans + cnt2);
    while(cnt2 < k){
        ans[cnt2++] = l;
    }
    for(ll i = 0;i < k;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}
///i am losing my mind

Compilation message (stderr)

road_construction.cpp: In function 'll del(ll, ll, ll)':
road_construction.cpp:67:8: warning: unused variable 'rightside' [-Wunused-variable]
   67 |     ll rightside = rid;
      |        ^~~~~~~~~

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