Submission #1195734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195734		byunjaewoo	Road Construction (JOI21_road_construction)	C++20	0 / 100	10137 ms	1107412 KiB

road_construction

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=250010, INF=4e9;
int n, k, x[N], y[N], v=INF+1;
array<int, 2> a[N];
vector<int> com, vec;

class seg {
public:
    void update(int k) {
        vec.push_back(k);
        for(int i=k; i<=n; i+=i&-i) tree[i]++;
    }
    int query(int k) {
        int ret=0;
        for(int i=k; i>=1; i-=i&-i) ret+=tree[i];
        return ret;
    }
    int query(int l, int r) {return query(r)-query(l-1);}
    void clear() {
        for(int k:vec) {
            for(int i=k; i<=n; i+=i&-i) tree[i]=0;
        }
        vec.clear();
    }
private:
    int tree[N];
    vector<int> vec;
}T;

int f(int t) {
    int ret=0;
    vector<array<int, 3>> p;
    for(int i=1; i<=n; i++) {
        p.push_back({a[i][0]+a[i][1], INF, lower_bound(com.begin(), com.end(), a[i][0]-a[i][1])-com.begin()+1});
        int l=lower_bound(com.begin(), com.end(), a[i][0]-a[i][1]-t)-com.begin()+1;
        int r=lower_bound(com.begin(), com.end(), a[i][0]-a[i][1]+t+1)-com.begin();
        p.push_back({a[i][0]+a[i][1]-t, l, -r}), p.push_back({a[i][0]+a[i][1]+t+1, l, r});
    }
    sort(p.begin(), p.end());
    for(auto [x, l, r]:p) {
        if(l==INF) T.update(r);
        else if(l>0) ret+=T.query(l, r);
        else ret-=T.query(-l, r);
    }
    T.clear();
    return (ret-n)/2;
}

void g(int s, int e, int t) {
    if(s>=e) return;
    int m=(s+e)/2, ret=0;
    priority_queue<int> pq;
    vector<array<int, 2>> vl, vr;
    for(int i=s; i<=m; i++) vl.push_back({y[i], x[i]+y[i]});
    for(int i=m+1; i<=e; i++) vr.push_back({y[i], x[i]+y[i]});
    sort(vl.begin(), vl.end()), sort(vr.begin(), vr.end());
    for(int i=0, j=0; i<vr.size(); i++) {
        while(j<vl.size() && vl[j][0]<=vr[i][0]) pq.push(vl[j][1]), j++;
        vector<int> tmp;
        while(!pq.empty() && pq.top()>=vr[i][1]-t) vec.push_back(vr[i][1]-pq.top()), tmp.push_back(pq.top()), pq.pop();
        for(int t:tmp) pq.push(t);
    }
    g(s, m, t), g(m+1, e, t);
}


void g2(int s, int e, int t) {
    if(s>=e) return;
    int m=(s+e)/2, ret=0;
    priority_queue<int> pq;
    vector<array<int, 2>> vl, vr;
    for(int i=s; i<=m; i++) vl.push_back({y[i], x[i]-y[i]});
    for(int i=m+1; i<=e; i++) vr.push_back({y[i], x[i]-y[i]});
    sort(vl.rbegin(), vl.rend()), sort(vr.rbegin(), vr.rend());
    for(int i=0, j=0; i<vr.size(); i++) {
        while(j<vl.size() && vl[j][0]>vr[i][0]) pq.push(vl[j][1]), j++;
        vector<int> tmp;
        while(!pq.empty() && pq.top()>=vr[i][1]-t) vec.push_back(vr[i][1]-pq.top()), tmp.push_back(pq.top()), pq.pop();
        for(int t:tmp) pq.push(t);
    }
    g2(s, m, t), g2(m+1, e, t);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>a[i][0]>>a[i][1], com.push_back(a[i][0]-a[i][1]);
    sort(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++) x[i]=a[i][0], y[i]=a[i][1];
    for(int s=0, e=INF; s<=e; ) {
        int m=(s+e)/2;
        if(f(m)>=k) v=m, e=m-1;
        else s=m+1;
    }
    g(1, n, v-1), g2(1, n, v-1);
    while(vec.size()<k) vec.push_back(v);
    sort(vec.begin(), vec.end());
    for(int i=0; i<k; i++) cout<<vec[i]<<"\n";
    return 0;
}

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