Submission #1246984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246984		raphaeltfa	Road Construction (JOI21_road_construction)	C++20	100 / 100	611 ms	13668 KiB

road_construction

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

const int inf =  1e18;

struct point{
    int x, y, id;
    bool operator<(const point &other) const {
        if(x == other.x) return y < other.y;
        return x < other.x;
    }
};

int dist(const point &a, const point &b){
    return abs(a.x - b.x) + abs(a.y - b.y);
}

void solve(){
    int n, k; cin >> n >> k;
    vector<point> base(n);
    priority_queue<int> pq;
    for(int i = 0; i < k; i++) pq.push(inf);
    for(int i = 0; i < n; i++){
        cin >> base[i].x >> base[i].y;
        base[i].id = i; 
    } sort(base.begin(), base.end());
    int maxi = pq.top();
    set<tuple<int, int, int>> sts;
    for(int i = 0; i < n; i++){
        tuple<int, int, int> tmp = make_tuple(base[i].y - maxi, -inf, base[i].id);
        set<tuple<int, int, int>>::iterator it = sts.lower_bound(tmp);
        while(it != sts.end() && get<0>(*it) <= base[i].y + maxi){
            point cur = {get<1>(*it), get<0>(*it), get<2>(*it)};
            if(dist(cur, base[i]) < maxi) { 
                pq.pop();
                pq.push(dist(cur, base[i]));
                maxi = pq.top();
            } if(cur.x < base[i].x - maxi) it = sts.erase(it);
            else it++;
        } sts.insert({base[i].y, base[i].x, base[i].id});
    } vector<int> rev_k(k);
    for(int i = 0; i < k; i++) rev_k[i] = pq.top(), pq.pop();
    for(int i = 0; i < k; i++) cout << rev_k[k - 1 - i] << endl;  
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    while(test--) solve();
}

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