Submission #995555

#	Time	Username	Problem	Language	Result	Execution time	Memory
995555		snpmrnhlol	Road Construction (JOI21_road_construction)	C++17	0 / 100	362 ms	12456 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
const int N = 25e4;
const int inf = 1e9;
mt19937 rng;
struct treap{
    int l,r;
    int x,y;
    int val;
}v[N + 1];
struct point{
    int x,y;
}v2[N];
int cnt = 1;
int lid,rid;
int n,k,cnt2 = 0;
int ans[N + 1];
void dbgtreap(int 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);
}
int mergetreap(int l, int 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(int node, int nr, int 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;
    }
}
int ins(int p, int x, int y, int 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;
}
int del(int p, int x, int val){
    splittreap(p, x, val - 1);
    int leftside = lid;
    int rightside = rid;
    splittreap(rid, x, val);
    int id = mergetreap(leftside, rid);
    return id;
}
void add(int pt,int x,int 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);
}
int get(int x){
    cnt = 1;
    cnt2 = 0;
    int treapid = 0;
    int pt = 0;
    for(int 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);
        int p1 = lid;
        splittreap(rid,v2[i].y + x + 1,-inf);
        int p2 = lid;
        int 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(int 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;
    });
    int l = 0,r = inf;
    while(l != r){
        int 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(int i = 0;i < k;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}
///i am losing my mind

Compilation message (stderr)

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

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