Submission #1219502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219502		Gray	Construction of Highway (JOI18_construction)	C++20	0 / 100	2 ms	584 KiB

construction

#include <algorithm>
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
const ll INF = 2e18;
using namespace std;

struct SegTree{
    vector<pair<ll, ll>> t;
    ll rsz;
    SegTree(ll N){
        t.resize(N*4, {-INF, -1});
        rsz=N;
    }
    void update(ll tl, ll tr, ll v, ll i, ll x, ll val){
        if (tl==tr){
            t[v] = {x, val};
        }else{
            ll tm = (tl+tr)/2;
            if (i<=tm) update(tl, tm, v*2, i, x, val);
            else update(tm+1, tr, v*2+1, i, x, val);
            t[v]=max(t[v*2], t[v*2+1]);
        }
    }
    void update(ll i, ll x, ll val){
        update(0, rsz-1, 1, i, x, val);
    }
    pair<ll, ll> query(ll tl, ll tr, ll v, ll l, ll r){
        if (tl==l and tr==r) return t[v];
        else if (l>r) return {-INF, -1};
        else{
            ll tm = (tl+tr)/2;
            return max(query(tl, tm, v*2, l, min(r, tm)), query(tm+1, tr, v*2+1, max(l, tm+1), r));
        }
    }
    ll query(ll l, ll r){
        return query(0, rsz-1, 1, l, r).ss;
    }
};

struct Fenwick{
    vector<pair<ll, ll>> log;
    vector<ll> tr;
    ll off, n;
    Fenwick(ll N){
        tr.resize(N+21); off=10; n=N+20;
    }
    void add(ll i, ll x){
        i+=off; log.push_back({i, x});
        for (; i<=n; i+=(-i&i)) tr[i]+=x;
    }
    ll query(ll i){
        i+=off; ll res=0; for (; i; i-=(-i&i)) res+=tr[i];
        return res;
    }
    void clear(){
        for (auto [i, x]:log){
            for (; i<=n; i+=(-i&i)) tr[i]-=x;
        }
        log.clear();
    }
};

void gen(ll u, ll p, vector<vector<ll>> &A, vector<vector<ll>> &bin, vector<array<ll, 2>> &rng, ll &timer){
    bin[u][0]=p; rng[u][0]=timer; timer++;
    for (ll i=1; i<20; i++) bin[u][i]=bin[bin[u][i-1]][i-1];
    for (auto v:A[u]){
        if (v==p) continue;
        gen(v, u, A, bin, rng, timer);
    }
    rng[u][1]=timer-1;
}

int main() {
    ll n; cin >> n;
    vector<array<ll, 3>> a(n+1), b;
    vector<ll> _bs;
    for (ll i=1; i<=n; i++){
        cin >> a[i][0]; _bs.push_back(a[i][0]);
    }
    sort(_bs.begin(), _bs.end());
    _bs.erase(unique(_bs.begin(), _bs.end()), _bs.end());
    for (auto &x:a){
        x[0]=lower_bound(_bs.begin(), _bs.end(), x[0])-_bs.begin();
    }
    vector<vector<ll>> A(n+1);
    for (ll i=1; i<n; i++){
        ll u, v; cin >> u >> v; a[v][1]=i; a[v][2]=v;
        A[u].push_back(v);
    }
    vector<vector<ll>> bin(n+1, vector<ll>(20));
    vector<array<ll, 2>> rng(n+1); ll timer=0;
    gen(1, 0, A, bin, rng, timer);
    b=a;
    sort(b.begin()+2, b.end(), [&](auto &op1, auto &op2)->bool{ return op1[1]<op2[1]; });
    SegTree val(n); val.update(0, 0, a[1][0]);
    vector<ll> res(n-1); rng[0] = {0, -1};
    for (ll i=2; i<=n; i++){
        ll v = b[i][2]; ll p = bin[v][0];
        ll cur = val.query(rng[p][0], rng[p][1]);
        Fenwick tr(n);
        while (true){
            ll up=p, jp=1;
            for (ll j=19; j>=0; j--){
                if (val.query(rng[bin[up][j]][0], rng[bin[up][j]][1])==cur) {
                    up=bin[up][j]; jp+=(1<<j);
                }
            }
            // cout << p << " - " << up << " " << jp << " * " << tr.query(cur) << ln;
            res[b[i][1]-1]+=tr.query(cur)*jp;
            tr.add(cur, jp);
            if (up==1) break;
            up=bin[up][0]; cur = val.query(rng[up][0], rng[up][1]); p=up;
        }
        // cout << "Pos: " << v << " - " << rng[v][0] << endl;
        val.update(rng[v][0], i, a[v][0]);
    }
    for (ll i=0; i<n-1; i++) cout << res[i] << ln;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 9
• Subtask 3: 0 / 84