Submission #391219

#	Time	Username	Problem	Language	Result	Execution time	Memory
391219		Jarif_Rahman	Road Construction (JOI21_road_construction)	C++17	100 / 100	3529 ms	618716 KiB

road_construction

#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 (stderr)

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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35