Submission #1171499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171499		OI_Account	Road Construction (JOI21_road_construction)	C++20	100 / 100	1949 ms	481676 KiB

road_construction

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

typedef long long ll;

const int N = 250'000;
const int S = 30'000'000;
const ll INF = 1'000'000'000'000'000'000;

int n, k;
pair<ll, ll> p[N + 10];
int counter, r1[N + 10], r2[N + 10];
int root1, root2, tmp[N + 10];
int lft[S + 10], rght[S + 10];
pair<ll, int> seg[S + 10];
set<pair<ll, int>> s;
ll ans[N + 10];

void readInput() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> p[i].second >> p[i].first;
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i++)
        swap(p[i].first, p[i].second);
}

pair<ll, int> get(int st, int en, int id, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return {INF, 0};
    if (st <= l && r <= en)
        return seg[id];
    int mid = (l + r) >> 1;
    return min(get(st, en, lft[id], l, mid), get(st, en, rght[id], mid, r));
}

int copyVer(int id) {
    int u = ++counter;
    lft[u] = lft[id];
    rght[u] = rght[id];
    seg[u] = seg[id];
    return u;
}

int update(int idx, ll val, int id, int l = 1, int r = n + 1) {
    if (idx < l || r <= idx)
        return id;
    id = copyVer(id);
    if (l + 1 == r) {
        seg[id] = {val, l};
        return id;
    }
    int mid = (l + r) >> 1;
    lft[id] = update(idx, val, lft[id], l, mid);
    rght[id] = update(idx, val, rght[id], mid, r);
    seg[id] = min(seg[lft[id]], seg[rght[id]]);
    return id;
}

void build(int id, int l = 1, int r = n + 1) {
    if (l + 1 == r) {
        seg[id] = {INF, l};
        return;
    }
    lft[id] = ++counter;
    rght[id] = ++counter;
    int mid = (l + r) >> 1;
    build(lft[id], l, mid);
    build(rght[id], mid, r);
    seg[id] = min(seg[lft[id]], seg[rght[id]]);
}

void calcBase() {
    counter = 1;
    root1 = root2 = 1;
    build(1);
}

void calcR() {
    vector<pair<ll, int>> vec;
    for (int i = 1; i <= n; i++)
        vec.push_back({p[i].first, i});
    sort(vec.begin(), vec.end());
    for (auto [val, i]: vec) {
        root1 = update(i, p[i].second - p[i].first, root1);
        root2 = update(i, -p[i].second - p[i].first, root2);
        r1[i] = root1;
        r2[i] = root2;
    }
}

void calcNext(int i) {
    if (tmp[i]) {
        r1[i] = update(tmp[i], INF, r1[i]);
        r2[i] = update(tmp[i], INF, r2[i]);
    }
    pair<ll, int> res1 = get(i + 1, n + 1, r1[i]);
    pair<ll, int> res2 = get(1, i, r2[i]);
    res1.first += p[i].first - p[i].second;
    res2.first += p[i].first + p[i].second;
    pair<ll, int> res = min(res1, res2);
    s.insert({res.first, i});
    tmp[i] = res.second;
}

void init() {
    for (int i = 1; i <= n; i++)
        calcNext(i);
}

void calcAns() {
    for (int i = 1; i <= k; i++) {
        pair<ll, int> tmp = *s.begin();
        s.erase(s.begin());
        cout << tmp.first << '\n';
        calcNext(tmp.second);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcBase();
    calcR();
    init();
    calcAns();
    return 0;
}

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