Submission #1094121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094121		thangdz2k7	Road Construction (JOI21_road_construction)	C++17	100 / 100	1390 ms	529472 KiB

road_construction

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using pli = pair <ll, int>;
using vi = vector <int>;

const int N = 3e5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

static char buf[1000 << 20];
void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*) &buf[i -= s];
}
void operator delete(void*) {}

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fd(sr, x) (lower_bound(sr.begin(), sr.end(), x) - sr.begin())
#define uq(sr) (sr).erase(unique(all((sr))), (sr).end())
#define szv(v) (int((v).size()))

#define left __left__
#define right __right__

const pli inf = {1e12, -1};

int n, k;

struct Node {
    Node *left, *right;
    pli Min = inf;

    Node (pli val){
        left = nullptr; right = nullptr; Min = val;
    }

    Node (Node *left, Node *right){
        this -> left = left;
        this -> right = right;
        this -> Min = min(left -> Min, right -> Min);
    }
};

Node *T[2][N];

Node *build(int l = 0, int r = n - 1){
    if (l == r) return new Node(inf);

    int mid = l + r >> 1;
    return new Node(build(l, mid), build(mid + 1, r));
}

Node *update(Node *old, int u, pli val, int l = 0, int r = n - 1){
    if (l == r) return new Node(val);

    auto &left = old -> left;
    auto &right = old -> right;
    int mid = l + r >> 1;
    if (mid >= u) return new Node(update(left, u, val, l, mid), right);
    return new Node(left, update(right, u, val, mid + 1, r));
}

pli get(Node *cur, int u, int v, int l = 0, int r = n - 1){
    if (r < u || v < l) return inf;
    if (u <= l && r <= v) return cur -> Min;

    int mid = l + r >> 1;
    return min(get(cur -> left, u, v, l, mid), get(cur -> right, u, v, mid + 1, r));
}

ll upd[2][N], qry[2][N], Min_pair[2][N];
pair <int, int> seg[2][N];

void solve(){
    cin >> n >> k;
    vector <ii> tower(n);
    for (int i = 0; i < n; ++ i) cin >> tower[i].fi >> tower[i].se;
    sort(all(tower)); vector <ii> sr;
    for (int i = 0; i < n; ++ i) sr.pb({tower[i].se, i});
    sort(all(sr)); uq(sr); vector <int> fake(n);

    for (int t : {0, 1}) T[t][0] = build();
    priority_queue <pair <pli, int>, vector <pair <pli, int>>, greater <pair <pli, int>>> qu;
    for (int i = 0; i < n; ++ i) {
        auto [X, Y] = tower[i];
        fake[i] = fd(sr, ii(Y, i));
        qry[0][i] = X + Y, qry[1][i] = X - Y;
        for (int t : {0, 1}){
            int u = 0, v = fake[i];
            if (t) u = fake[i] + 1, v = n - 1;
            seg[t][i] = ii(u, v);
            if (u <= v){
                auto [dist, idx] = get(T[t][i], u, v);
                if (idx > -1){
                    qu.push({{dist + qry[t][i], i}, t});
                    Min_pair[t][i] = idx;
                }
            }
        }

        upd[0][i] = -X - Y, upd[1][i] = -X + Y;
        for (int t : {0, 1}) T[t][i + 1] = update(T[t][i], fake[i], {upd[t][i], i});
    }

    while (k --){
        auto [skf, t] = qu.top(); qu.pop();
        auto [di, i] = skf; cout << di << endl;
        int idxMin = Min_pair[t][i];
        T[t][i] = update(T[t][i], fake[idxMin], inf);
        auto [u, v] = seg[t][i];
        if (u <= v){
            auto [dist, idx] = get(T[t][i], u, v);
            if (idx > -1){
                qu.push({{dist + qry[t][i], i}, t});
                Min_pair[t][i] = idx;
            }
        }
    }
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

road_construction.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
road_construction.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
road_construction.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
road_construction.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
road_construction.cpp: In function 'Node* build(int, int)':
road_construction.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In function 'Node* update(Node*, int, pli, int, int)':
road_construction.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In function 'pli get(Node*, int, int, int, int)':
road_construction.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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