제출 #1159537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159537		PagodePaiva	Road Construction (JOI21_road_construction)	C++20	65 / 100	10095 ms	304940 KiB

road_construction

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")

#define endl '\n'

using namespace std;

const int N = 1e6+10;
const long long L = 0, R = 8e9;
const long long C = 4e9;

struct Segtree{
    int tree[4*N], lf[4*N], rf[4*N], sz;
    int join(int a, int b){
        return a+b;
    }
    void start(){
        memset(tree, 0, sizeof tree);
        memset(lf, -1, sizeof lf);
        memset(rf, -1, sizeof rf);
    }
    void build(){
        tree[1] = 0;
        lf[1] = rf[1] = -1;
        sz = 1;
    }
    int calc(int node){
        int res = 0;
        if(lf[node] != -1) res += tree[lf[node]];
        if(rf[node] != -1) res += tree[rf[node]];
        return res;
    }
    void update(int node, long long l, long long r, long long pos, int val){
        if(l == r){
            tree[node] += val;
            return;
        }
        long long mid = (l+r)/2;
        if(l <= pos and pos <= mid){
            if(lf[node] == -1){
                sz++;
                lf[node] = sz;
                tree[lf[node]] = 0;
            }
            update(lf[node], l, mid, pos, val);
        }
        else{
            if(rf[node] == -1){
                sz++;
                rf[node] = sz;
                tree[rf[node]] = 0;
            }
            update(rf[node], mid+1, r, pos, val);
        }
        tree[node] = calc(node);
        return;
    }
    int query(int node, long long l, long long r, long long tl, long long tr){
        if(node == -1) return 0;
        if(l > tr or tl > r) return 0;
        if(l <= tl and tr <= r) return tree[node];
        long long mid = (tl+tr)/2;
        return join(query(lf[node], l, r, tl, mid), query(rf[node], l, r, mid+1, tr));
    }
    void clear(int node, long long l, long long r){
        long long mid = (l+r)/2;
        if(lf[node] != -1) clear(lf[node], l, mid);
        lf[node] = -1;
        if(rf[node] != -1) clear(rf[node], mid+1, r);
        rf[node] = -1;
        tree[node] = 0;
        sz = 1;
        return;
    }
} seg;

vector <long long> answer;
long long atx, aty;

struct SegtreeSet{
    int tree[4*N], lf[4*N], rf[4*N], sz;
    map <long long, int> ss[4*N];
    int join(int a, int b){
        return a+b;
    }
    void start(){
        memset(tree, 0, sizeof tree);
        memset(lf, -1, sizeof lf);
        memset(rf, -1, sizeof rf);
    }
    void build(){
        tree[1] = 0;
        lf[1] = rf[1] = -1;
        sz = 1;
    }
    int calc(int node){
        int res = 0;
        if(lf[node] != -1) res += tree[lf[node]];
        if(rf[node] != -1) res += tree[rf[node]];
        return res;
    }
    void updateadd(int node, long long l, long long r, long long pos, int val){
        if(l == r){
            tree[node]++;
            ss[node][val]++;
            return;
        }
        long long mid = (l+r)/2;
        if(l <= pos and pos <= mid){
            if(lf[node] == -1){
                sz++;
                lf[node] = sz;
                tree[lf[node]] = 0;
            }
            updateadd(lf[node], l, mid, pos, val);
        }
        else{
            if(rf[node] == -1){
                sz++;
                rf[node] = sz;
                tree[rf[node]] = 0;
            }
            updateadd(rf[node], mid+1, r, pos, val);
        }
        tree[node] = calc(node);
        return;
    }
    void updateremove(int node, long long l, long long r, long long pos, int val){
        if(l == r){
            tree[node]--;
            ss[node][val]--;
            return;
        }
        long long mid = (l+r)/2;
        if(l <= pos and pos <= mid){
            if(lf[node] == -1){
                sz++;
                lf[node] = sz;
                tree[lf[node]] = 0;
            }
            updateremove(lf[node], l, mid, pos, val);
        }
        else{
            if(rf[node] == -1){
                sz++;
                rf[node] = sz;
                tree[rf[node]] = 0;
            }
            updateremove(rf[node], mid+1, r, pos, val);
        }
        tree[node] = calc(node);
        return;
    }
    void query(int node, long long l, long long r, long long tl, long long tr){
        if(node == -1) return;
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
           // cout << tl << ' ' << tr << endl;
            if(tl == tr){
                if(ss[node].empty()) return;
                for(auto [valor, qtd] : ss[node]){
                    for(int i = 0;i < qtd;i++) answer.push_back(max(abs(atx-valor), abs(aty-(tl-C))));
                }
                return;
            }
            long long mid = (tl+tr)/2;
            if(lf[node] != -1){
                if(tree[lf[node]] != 0) query(lf[node], l, r, tl, mid);
            }
            if(rf[node] != -1){
                if(tree[rf[node]] != 0) query(rf[node], l, r, mid+1, tr);
            }
            return;
        }
        long long mid = (tl+tr)/2;
        query(lf[node], l, r, tl, mid);
        query(rf[node], l, r, mid+1, tr);
        return;
    }
    void clear(int node, long long l, long long r){
        long long mid = (l+r)/2;
        if(lf[node] != -1) clear(lf[node], l, mid);
        lf[node] = -1;
        if(rf[node] != -1) clear(rf[node], mid+1, r);
        rf[node] = -1;
        tree[node] = 0;
        sz = 1;
        return;
    }
} seg2;

vector <pair <long long, long long>> v;

long long solve(long long D){
    seg.clear(1, L, R);
    seg.build();
    int r = 0;
    long long res = 0;
    for(int i = 0;i < v.size();i++){
        while(r < v.size()){
            if(v[r].first-v[i].first > D) break;
            seg.update(1, L, R, v[r].second+C, +1);
            r++;
        }
        res += seg.query(1, v[i].second-D+C, v[i].second+D+C, L, R)-1;
        seg.update(1, L, R, v[i].second+C, -1);
    }
    return res;
}

void solve2(long long D){
    seg2.start();
    seg2.clear(1, L, R);
    seg2.build();
    int r = 0;
    long long res = 0;
    for(int i = 0;i < v.size();i++){
        atx = v[i].first;
        aty = v[i].second;
        while(r < v.size()){
            if(v[r].first-v[i].first > D) break;
            seg2.updateadd(1, L, R, v[r].second+C, v[r].first);
            r++;
        }
        seg2.updateremove(1, L, R, v[i].second+C, v[i].first);
        seg2.query(1, v[i].second-D+C, v[i].second+D+C, L, R);
    }
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 0;i < n;i++){
        int a, b;
        cin >> a >> b;
        v.push_back({a+b, b-a});
    }
    sort(v.begin(), v.end());
    seg.start();
    seg.build();
    long long l = 0, r = 4e9;
    long long ans = r;
    while(l <= r){
        long long mid = (l+r)/2;
        if(solve(mid) >= k){
            r = mid-1;
        }
        else{
            ans = mid;
            l = mid+1;
        }
    }
    solve2(ans);
    while(answer.size() < k){
        answer.push_back(ans+1);
    }
    sort(answer.begin(), answer.end());
    for(auto x : answer){
        cout << x << '\n';
    }
    return 0;    
}

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