Submission #1195702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195702		byunjaewoo	Road Construction (JOI21_road_construction)	C++20	5 / 100	10093 ms	24068 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], v1=INF+1, v2=INF+1;
array<int, 2> a[N];
vector<int> vec1, vec2;

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 s, int e, int t) {
    if(s>=e) return 0;
    int m=(s+e)/2, ret=0;
    vector<int> com;
    vector<array<int, 2>> vl, vr;
    for(int i=s; i<=m; i++) com.push_back(x[i]+y[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(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
    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]) T.update(lower_bound(com.begin(), com.end(), vl[j][1])-com.begin()+1), j++;
        ret+=T.query(lower_bound(com.begin(), com.end(), vr[i][1]-t)-com.begin()+1, com.size());
    }
    T.clear();
    return ret+f(s, m, t)+f(m+1, e, t);
}

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) vec1.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);
}


int f2(int s, int e, int t) {
    if(s>=e) return 0;
    int m=(s+e)/2, ret=0;
    vector<int> com;
    vector<array<int, 2>> vl, vr;
    for(int i=s; i<=m; i++) com.push_back(x[i]-y[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(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
    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]) T.update(lower_bound(com.begin(), com.end(), vl[j][1])-com.begin()+1), j++;
        ret+=T.query(lower_bound(com.begin(), com.end(), vr[i][1]-t)-com.begin()+1, com.size());
    }
    T.clear();
    return ret+f2(s, m, t)+f2(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) vec2.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];
    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(1, n, m)>=k) v1=m, e=m-1;
        else s=m+1;
    }
    g(1, n, v1-1);
    if(v1<=INF) while(vec1.size()<k) vec1.push_back(v1);
    for(int s=0, e=INF; s<=e; ) {
        int m=(s+e)/2;
        if(f2(1, n, m)>=k) v2=m, e=m-1;
        else s=m+1;
    }
    g2(1, n, v2-1);
    if(v2<=INF) while(vec2.size()<k) vec2.push_back(v2);
    for(int i:vec2) vec1.push_back(i);
    sort(vec1.begin(), vec1.end());
    for(int i=0; i<k; i++) cout<<vec1[i]<<"\n";
    return 0;
}

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