Submission #241909

#	Time	Username	Problem	Language	Result	Execution time	Memory
241909		osaaateiasavtnl	Construction of Highway (JOI18_construction)	C++17	100 / 100	1335 ms	23972 KiB

construction

#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1e5+7, LG = 20;
int n, a[N], par[N];
ii d[N];
vector <int> tree[N];

int to[N][LG], h[N];
int l[N], r[N], ptr = -1;
void dfs(int u) {
    to[u][0] = par[u];
    for (int i = 1; i < LG; ++i)
        to[u][i] = to[to[u][i - 1]][i - 1];

    l[u] = ++ptr;    

    for (int v : tree[u]) {
        h[v] = h[u]+1;
        dfs(v);        
    }   

    r[u] = ptr;
}   

int mx[N << 2];
void upd(int v, int tl, int tr, int i, int x) {
    mx[v] = x;
    if (tl == tr) 
        return;
    int tm = (tl + tr) >> 1;
    if (i <= tm)
        upd(v * 2 + 1, tl, tm, i, x);
    else
        upd(v * 2 + 2, tm + 1, tr, i, x);
}
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl)
        return -1;
    if (l <= tl && tr <= r)
        return mx[v];
    int tm = (tl + tr) >> 1;
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}

int val[N];

int prv[N];
int last(int u) {
    return prv[u] = get(0, 0, N, l[u], r[u]);
}

int getval(int u, int ls) {
    if (ls == -1)
        return a[u];
    else
        return val[ls];
}

struct Fen {
int f[N];
void add(int i, int x) {
    for (; i < N; i |= i + 1) 
        f[i] += x;
}   
void clear(int i) {
    for (; i < N; i |= i + 1)
        f[i] = 0;
}   
int get(int i) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i) ans += f[i];
    return ans;
}   
int get(int l, int r) {
    return get(r) - get(l - 1);
}   
} f;

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    for (int i = 0; i < (N << 2); ++i)
        mx[i] = -1;

    cin >> n;
    vector <int> c;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        c.app(a[i]);
    }   
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(all(c), a[i]) - c.begin();

    for (int t = 0; t < n - 1; ++t) {
        int u, v;
        cin >> u >> v;
        tree[u].app(v);
        par[v] = u;
        d[t] = mp(u,v);
    }   

    par[1] = 1;
    dfs(1);

    int sum = 0;
    for (int i = 0; i < N; ++i)
        prv[i] = -1;
    for (int t = 0; t < n - 1; ++t) {
        int u, v;
        tie(u, v) = d[t];

        vector <ii> path;
        while (1) {
            int up = u;
            int w = last(u);
            for (int i = LG - 1; i >= 0; --i)
                if (prv[to[up][i]] <= w && last(to[up][i]) == w)
                    up = to[up][i];
            path.app(mp(getval(u, w), h[u] - h[up] + 1));
            if (up == 1)
                break;
            else
                u = par[up];
        }   

        val[t] = a[v];
        upd(0, 0, N, l[v], t);

        sum += path.size();
        if (sum > 20 * n)
            exit(1);

        ll ans = 0;
        for (auto e : path) {
            ans += f.get(e.f - 1) * e.s;
            f.add(e.f, e.s);
        }   
        cout << ans << endl;
        for (auto e : path)
            f.clear(e.f);
    }   
}

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