oj.uz

Submission #391219

# Submission time Handle Problem Language Result Execution time Memory
391219 2021-04-18T09:22:34 Z Jarif_Rahman Road Construction (JOI21_road_construction) C++17
100 / 100
 3529 ms 618716 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf  = 1e18;
struct persistent_segtree{
    struct node{
        pair<ll, int> mn;
        int l, r;
        node(){
            mn = {inf, -1};
            l = -1, r = -1;
        }
        node(pair<ll, int> _mn){
            mn = _mn;
            l = -1, r = -1;
        }
        node(pair<ll, int> _mn, int _l, int _r){
            l = _l, r = _r, mn = _mn;
        }
    };
    vector<node> v;
    int k;
    persistent_segtree(int n){
        k = 1;
        while(k <= n) k*=2; k*=2;
        v.resize(k, node({inf, -1}));
        for(int i = 0; i < k/2; i++) v[i].mn.sc = i;
        for(int i = 1; 2*i+1 < k; i++) v[i].l = 2*i, v[i].r = 2*i+1, v[i].mn.sc = v[2*i].mn.sc;
    }
    int upd(int nd, int a, int b, int in, pair<ll, int> x){
        if(a == b){
            v.pb(node(x));
            return (int)v.size() - 1;
        }
        int md = (a+b)/2;
        if(in <= md){
            int rt = upd(v[nd].l, a, md, in, x);
            v.pb(node(min(v[v[nd].r].mn,v[rt].mn), rt, v[nd].r));
            return (int)v.size()-1;
        }
        else{
            int rt = upd(v[nd].r, md+1, b, in, x);
            v.pb(node(min(v[v[nd].l].mn,v[rt].mn), v[nd].l, rt));
            return (int)v.size()-1;
        }
    }
    int upd(int nd, int in, ll x){
        return upd(nd, 0, k/2-1, in, {x, in});
    }
    pair<ll, int> smn(int l, int r, int nd, int a, int b){
        if(a > r || b < l){
            return {inf, -1};
        }
        if(a >= l && b <= r){
            return v[nd].mn;
        }
        int md = (a+b)/2;
        return min(smn(l, r, v[nd].l, a, md), smn(l, r, v[nd].r, md+1, b));
    }
    pair<ll, int> smn(int nd, int l, int r){
        return smn(l, r, nd, 0, k/2-1);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<pair<ll, ll>> v(n);
    for(auto &p: v) cin >> p.f >> p.sc;
    sort(v.begin(), v.end());
    vector<pair<ll, int>> yyy(n);
    for(int i = 0; i < n; i++) yyy[i] = {v[i].sc, i};
    vector<int> yy(n);
    sort(yyy.begin(), yyy.end());
    for(int i = 0; i < n; i++) yy[yyy[i].sc] = i;
    persistent_segtree ps1(n), ps2(n);
    priority_queue<tuple<ll, int, int, int>> pq;
    int id = 1;
    for(int i = 0; i < n; i++){
        auto a = ps1.smn(id, 0, yy[i]);
        auto b = ps2.smn(id, yy[i], n-1);
        a.f+=v[i].f+v[i].sc;
        b.f+=v[i].f-v[i].sc;
        if(b.f < a.f) swap(a, b);
        pq.push({-a.f, a.sc, id, i});
        int id0 = ps1.upd(id, yy[i], -v[i].f-v[i].sc);
        ps2.upd(id, yy[i], -v[i].f+v[i].sc);
        id = id0;
    }
    while(k--){
        auto [x, in, id, i] = pq.top();
        x*=-1;
        cout << x << "\n";
        pq.pop();
        int id0 = ps1.upd(id, in, inf);
        ps2.upd(id, in, inf);
        id = id0;
        auto a = ps1.smn(id, 0, yy[i]);
        auto b = ps2.smn(id, yy[i], n-1);
        a.f+=v[i].f+v[i].sc;
        b.f+=v[i].f-v[i].sc;
        if(b.f < a.f) swap(a, b);
        pq.push({-a.f, a.sc, id, i});
    }
}

Compilation message

road_construction.cpp: In constructor 'persistent_segtree::persistent_segtree(int)':
road_construction.cpp:29:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   29 |         while(k <= n) k*=2; k*=2;
      |         ^~~~~
road_construction.cpp:29:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   29 |         while(k <= n) k*=2; k*=2;
      |                             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 150240 KB Output is correct
2 Correct 878 ms 150276 KB Output is correct
3 Correct 811 ms 150380 KB Output is correct
4 Correct 743 ms 150464 KB Output is correct
5 Correct 846 ms 149496 KB Output is correct
6 Correct 6 ms 2940 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2321 ms 615960 KB Output is correct
2 Correct 2128 ms 615960 KB Output is correct
3 Correct 519 ms 150400 KB Output is correct
4 Correct 1545 ms 615784 KB Output is correct
5 Correct 1446 ms 616172 KB Output is correct
6 Correct 1434 ms 616172 KB Output is correct
7 Correct 1565 ms 615832 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 320388 KB Output is correct
2 Correct 1215 ms 320440 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 716 ms 318188 KB Output is correct
5 Correct 918 ms 320832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 320388 KB Output is correct
2 Correct 1215 ms 320440 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 716 ms 318188 KB Output is correct
5 Correct 918 ms 320832 KB Output is correct
6 Correct 1232 ms 320564 KB Output is correct
7 Correct 1233 ms 320372 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1224 ms 320408 KB Output is correct
11 Correct 714 ms 318248 KB Output is correct
12 Correct 920 ms 320648 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 150240 KB Output is correct
2 Correct 878 ms 150276 KB Output is correct
3 Correct 811 ms 150380 KB Output is correct
4 Correct 743 ms 150464 KB Output is correct
5 Correct 846 ms 149496 KB Output is correct
6 Correct 6 ms 2940 KB Output is correct
7 Correct 2294 ms 321844 KB Output is correct
8 Correct 2285 ms 321692 KB Output is correct
9 Correct 693 ms 150348 KB Output is correct
10 Correct 1525 ms 320700 KB Output is correct
11 Correct 1771 ms 320752 KB Output is correct
12 Correct 1050 ms 321480 KB Output is correct
13 Correct 1238 ms 320344 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 150240 KB Output is correct
2 Correct 878 ms 150276 KB Output is correct
3 Correct 811 ms 150380 KB Output is correct
4 Correct 743 ms 150464 KB Output is correct
5 Correct 846 ms 149496 KB Output is correct
6 Correct 6 ms 2940 KB Output is correct
7 Correct 2321 ms 615960 KB Output is correct
8 Correct 2128 ms 615960 KB Output is correct
9 Correct 519 ms 150400 KB Output is correct
10 Correct 1545 ms 615784 KB Output is correct
11 Correct 1446 ms 616172 KB Output is correct
12 Correct 1434 ms 616172 KB Output is correct
13 Correct 1565 ms 615832 KB Output is correct
14 Correct 1260 ms 320388 KB Output is correct
15 Correct 1215 ms 320440 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 716 ms 318188 KB Output is correct
18 Correct 918 ms 320832 KB Output is correct
19 Correct 1232 ms 320564 KB Output is correct
20 Correct 1233 ms 320372 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1224 ms 320408 KB Output is correct
24 Correct 714 ms 318248 KB Output is correct
25 Correct 920 ms 320648 KB Output is correct
26 Correct 2294 ms 321844 KB Output is correct
27 Correct 2285 ms 321692 KB Output is correct
28 Correct 693 ms 150348 KB Output is correct
29 Correct 1525 ms 320700 KB Output is correct
30 Correct 1771 ms 320752 KB Output is correct
31 Correct 1050 ms 321480 KB Output is correct
32 Correct 1238 ms 320344 KB Output is correct
33 Correct 3508 ms 618548 KB Output is correct
34 Correct 3529 ms 618548 KB Output is correct
35 Correct 2694 ms 618008 KB Output is correct
36 Correct 1786 ms 618716 KB Output is correct
37 Correct 1723 ms 618508 KB Output is correct
38 Correct 2115 ms 617808 KB Output is correct