oj.uz

Submission #1094119

# Submission time Handle Problem Language Result Execution time Memory
1094119 2024-09-28T13:49:16 Z thangdz2k7 Road Construction (JOI21_road_construction) C++17
100 / 100
 2257 ms 758228 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);}

#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:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In function 'Node* update(Node*, int, pli, int, int)':
road_construction.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In function 'pli get(Node*, int, int, int, int)':
road_construction.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 133124 KB Output is correct
2 Correct 279 ms 133200 KB Output is correct
3 Correct 260 ms 127828 KB Output is correct
4 Correct 232 ms 127568 KB Output is correct
5 Correct 271 ms 132104 KB Output is correct
6 Correct 4 ms 2904 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1178 ms 747452 KB Output is correct
2 Correct 1150 ms 747568 KB Output is correct
3 Correct 179 ms 127572 KB Output is correct
4 Correct 776 ms 747456 KB Output is correct
5 Correct 834 ms 747456 KB Output is correct
6 Correct 982 ms 747716 KB Output is correct
7 Correct 984 ms 746940 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 533684 KB Output is correct
2 Correct 995 ms 533932 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 531 ms 523756 KB Output is correct
5 Correct 663 ms 533940 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 533684 KB Output is correct
2 Correct 995 ms 533932 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 531 ms 523756 KB Output is correct
5 Correct 663 ms 533940 KB Output is correct
6 Correct 945 ms 533732 KB Output is correct
7 Correct 942 ms 533712 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 943 ms 533816 KB Output is correct
11 Correct 528 ms 523712 KB Output is correct
12 Correct 725 ms 533924 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 133124 KB Output is correct
2 Correct 279 ms 133200 KB Output is correct
3 Correct 260 ms 127828 KB Output is correct
4 Correct 232 ms 127568 KB Output is correct
5 Correct 271 ms 132104 KB Output is correct
6 Correct 4 ms 2904 KB Output is correct
7 Correct 1303 ms 411476 KB Output is correct
8 Correct 1290 ms 411460 KB Output is correct
9 Correct 288 ms 127936 KB Output is correct
10 Correct 637 ms 411208 KB Output is correct
11 Correct 787 ms 410868 KB Output is correct
12 Correct 613 ms 411636 KB Output is correct
13 Correct 731 ms 410184 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 133124 KB Output is correct
2 Correct 279 ms 133200 KB Output is correct
3 Correct 260 ms 127828 KB Output is correct
4 Correct 232 ms 127568 KB Output is correct
5 Correct 271 ms 132104 KB Output is correct
6 Correct 4 ms 2904 KB Output is correct
7 Correct 1178 ms 747452 KB Output is correct
8 Correct 1150 ms 747568 KB Output is correct
9 Correct 179 ms 127572 KB Output is correct
10 Correct 776 ms 747456 KB Output is correct
11 Correct 834 ms 747456 KB Output is correct
12 Correct 982 ms 747716 KB Output is correct
13 Correct 984 ms 746940 KB Output is correct
14 Correct 937 ms 533684 KB Output is correct
15 Correct 995 ms 533932 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 531 ms 523756 KB Output is correct
18 Correct 663 ms 533940 KB Output is correct
19 Correct 945 ms 533732 KB Output is correct
20 Correct 942 ms 533712 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 943 ms 533816 KB Output is correct
24 Correct 528 ms 523712 KB Output is correct
25 Correct 725 ms 533924 KB Output is correct
26 Correct 1303 ms 411476 KB Output is correct
27 Correct 1290 ms 411460 KB Output is correct
28 Correct 288 ms 127936 KB Output is correct
29 Correct 637 ms 411208 KB Output is correct
30 Correct 787 ms 410868 KB Output is correct
31 Correct 613 ms 411636 KB Output is correct
32 Correct 731 ms 410184 KB Output is correct
33 Correct 2257 ms 758160 KB Output is correct
34 Correct 1980 ms 758160 KB Output is correct
35 Correct 1274 ms 757672 KB Output is correct
36 Correct 1026 ms 758228 KB Output is correct
37 Correct 1143 ms 758196 KB Output is correct
38 Correct 1200 ms 756944 KB Output is correct