Submission #959913

#	Time	Username	Problem	Language	Result	Execution time	Memory
959913		alextodoran	Road Construction (JOI21_road_construction)	C++17	13 / 100	2009 ms	73044 KiB

road_construction

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 250000;

int N, K;
ll X[N_MAX + 2], Y[N_MAX + 2];
int order_x[N_MAX + 2], order_y[N_MAX + 2];
int nxt_x[N_MAX + 2], nxt_y[N_MAX + 2];

struct Candidate {
    int i, j;
    ll dist;
    Candidate (const int &_i, const int &_j) {
        i = _i; j = _j;
        if (i > j) {
            swap(i, j);
        }
        dist = max(abs(X[i] - X[j]), abs(Y[i] - Y[j]));
    }
};
bool operator < (const Candidate &a, const Candidate &b) {
    return make_tuple(a.dist, a.i, a.j) < make_tuple(b.dist, b.i, b.j);
}
set <Candidate> cands;

int curr_x[N_MAX + 2], curr_y[N_MAX + 2];

set <pair <int, int>> seen;

void update (int i) {
    curr_x[i] = nxt_x[curr_x[i]];
    curr_y[i] = nxt_y[curr_y[i]];
    if (curr_x[i] != 0) {
        cands.insert(Candidate(i, curr_x[i]));
    }
    if (curr_y[i] != 0) {
        cands.insert(Candidate(i, curr_y[i]));
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        ll x, y;
        cin >> x >> y;
        X[i] = y + x; Y[i] = y - x;
    }
    iota(order_x + 1, order_x + N + 1, 1);
    iota(order_y + 1, order_y + N + 1, 1);
    sort(order_x + 1, order_x + N + 1, [&] (const int &i, const int &j) {
        return X[i] < X[j];
    });
    sort(order_y + 1, order_y + N + 1, [&] (const int &i, const int &j) {
        return Y[i] < Y[j];
    });
    for (int i = 1; i <= N; i++) {
        nxt_x[order_x[i]] = order_x[i + 1];
        nxt_y[order_y[i]] = order_y[i + 1];
    }
    for (int i = 1; i <= N; i++) {
        curr_x[i] = curr_y[i] = i;
        update(i);
    }
    while (K--) {
        Candidate best = *cands.begin();
        int i = best.i, j = best.j; ll dist = best.dist;
        cands.erase(cands.begin());
        if (seen.find(make_pair(i, j)) != seen.end()) {
            K++; continue;
        }
        seen.insert(make_pair(i, j));
        cout << dist << "\n";
        update(i); update(j);
    }

    return 0;
}

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