oj.uz

Submission #1094121

# Submission time Handle Problem Language Result Execution time Memory
1094121 2024-09-28T13:52:42 Z thangdz2k7 Road Construction (JOI21_road_construction) C++17
100 / 100
 1390 ms 529472 KB 
// 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 90192 KB Output is correct
2 Correct 170 ms 89936 KB Output is correct
3 Correct 159 ms 86352 KB Output is correct
4 Correct 142 ms 86100 KB Output is correct
5 Correct 167 ms 88656 KB Output is correct
6 Correct 2 ms 2140 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 514592 KB Output is correct
2 Correct 722 ms 514444 KB Output is correct
3 Correct 151 ms 86096 KB Output is correct
4 Correct 562 ms 514384 KB Output is correct
5 Correct 579 ms 514804 KB Output is correct
6 Correct 596 ms 514644 KB Output is correct
7 Correct 605 ms 513876 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 378992 KB Output is correct
2 Correct 611 ms 378992 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 310 ms 364884 KB Output is correct
5 Correct 495 ms 378960 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 378992 KB Output is correct
2 Correct 611 ms 378992 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 310 ms 364884 KB Output is correct
5 Correct 495 ms 378960 KB Output is correct
6 Correct 652 ms 378964 KB Output is correct
7 Correct 656 ms 378992 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 677 ms 379176 KB Output is correct
11 Correct 302 ms 365140 KB Output is correct
12 Correct 428 ms 378996 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 90192 KB Output is correct
2 Correct 170 ms 89936 KB Output is correct
3 Correct 159 ms 86352 KB Output is correct
4 Correct 142 ms 86100 KB Output is correct
5 Correct 167 ms 88656 KB Output is correct
6 Correct 2 ms 2140 KB Output is correct
7 Correct 777 ms 285796 KB Output is correct
8 Correct 754 ms 285780 KB Output is correct
9 Correct 149 ms 86356 KB Output is correct
10 Correct 445 ms 285236 KB Output is correct
11 Correct 516 ms 285012 KB Output is correct
12 Correct 390 ms 285952 KB Output is correct
13 Correct 464 ms 284632 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 90192 KB Output is correct
2 Correct 170 ms 89936 KB Output is correct
3 Correct 159 ms 86352 KB Output is correct
4 Correct 142 ms 86100 KB Output is correct
5 Correct 167 ms 88656 KB Output is correct
6 Correct 2 ms 2140 KB Output is correct
7 Correct 748 ms 514592 KB Output is correct
8 Correct 722 ms 514444 KB Output is correct
9 Correct 151 ms 86096 KB Output is correct
10 Correct 562 ms 514384 KB Output is correct
11 Correct 579 ms 514804 KB Output is correct
12 Correct 596 ms 514644 KB Output is correct
13 Correct 605 ms 513876 KB Output is correct
14 Correct 626 ms 378992 KB Output is correct
15 Correct 611 ms 378992 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 310 ms 364884 KB Output is correct
18 Correct 495 ms 378960 KB Output is correct
19 Correct 652 ms 378964 KB Output is correct
20 Correct 656 ms 378992 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 677 ms 379176 KB Output is correct
24 Correct 302 ms 365140 KB Output is correct
25 Correct 428 ms 378996 KB Output is correct
26 Correct 777 ms 285796 KB Output is correct
27 Correct 754 ms 285780 KB Output is correct
28 Correct 149 ms 86356 KB Output is correct
29 Correct 445 ms 285236 KB Output is correct
30 Correct 516 ms 285012 KB Output is correct
31 Correct 390 ms 285952 KB Output is correct
32 Correct 464 ms 284632 KB Output is correct
33 Correct 1390 ms 529376 KB Output is correct
34 Correct 1366 ms 529472 KB Output is correct
35 Correct 876 ms 528464 KB Output is correct
36 Correct 698 ms 528980 KB Output is correct
37 Correct 687 ms 529232 KB Output is correct
38 Correct 809 ms 527656 KB Output is correct