Submission #1159511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159511		PagodePaiva	Road Construction (JOI21_road_construction)	C++20	0 / 100	2885 ms	2103804 KiB

road_construction

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+10;

struct Segtree{
    int tree[4*N], lf[4*N], rf[4*N], sz;
    int join(int a, int b){
        return a+b;
    }
    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, int l, int r, int pos, int val){
        if(l == r){
            tree[node] += val;
            return;
        }
        int mid = (l+r)/2;
        if(l <= pos and pos <= mid){
            if(lf[node] == -1){
                sz++;
                lf[node] = sz;
            }
            update(lf[node], l, mid, pos, val);
        }
        else{
            if(rf[node] == -1){
                sz++;
                rf[node] = sz;
            }
            update(rf[node], mid+1, r, pos, val);
        }
        tree[node] = calc(node);
        return;
    }
    int query(int node, int l, int r, int tl, int tr){
        if(node == -1) return 0;
        if(l > tr or tl > r) return 0;
        if(l <= tl and tr <= r) return tree[node];
        int 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, int l, int r){
        int 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;
    }
};

vector <pair <int, int>> v;

int main(){
    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());
    vector <int> ans;
    for(int i = 0;i < v.size();i++){
        for(int j = i+1;j < v.size();j++){
            ans.push_back(max(abs(v[i].first-v[j].first), abs(v[i].second-v[j].second)));
        }
    }
    sort(ans.begin(), ans.end());
    for(int i = 0;i < k;i++){
        cout << ans[i] << '\n';
    }
}

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