Submission #830849

#	Time	Username	Problem	Language	Result	Execution time	Memory
830849		vjudge1	Construction of Highway (JOI18_construction)	C++17	100 / 100	221 ms	86092 KiB

construction

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 100100;

vector < int > adj[N];
int sz[N], head[N], up[N], depth[N], C[N];
deque < pair < int, int > > HLD[N];
vector < pair < int, int > > V, edges; 
ll tree[N];
stack < pair < int, int > > st;

void upd(int pos, int val) {
    for(; pos < N; tree[pos] += val, pos += -pos&pos);
}

ll sum(int x) {
    ll ans = 0;
    for(; x; ans += tree[x], x ^= -x&x);
    return ans;
}

void dfs(int v) {
    if(!head[v]) {
        head[v] = v;
    }
    
    HLD[head[v]].push_back({C[v], 1});

    int mx = 0;
    for(auto &u : adj[v]) {
        if(!mx || sz[u] > sz[mx]) {
            mx = u;
        }
    }
    if(mx) {
        head[mx] = head[v];
    }
    for(auto &u : adj[v]) {
        dfs(u);
    }
}

ll cnt_inv() {
    ll ans = 0;
    for(auto &[x, cnt] : V) {
        ans += cnt * sum(x - 1);
        upd(x, cnt);
    }
    for(; !V.empty(); V.pop_back()) {
        upd(V.back().first, -V.back().second);
    }
    return ans;
}

void cut(int i, int k, int b) {
    for(int t = k; t;) {
        if(HLD[i].front().second <= t) {
            st.push(HLD[i].front());
            t -= st.top().second;
            HLD[i].pop_front();
        } else {
            st.push({HLD[i].front().first, t});
            HLD[i].front().second -= t;
            t = 0;
        }
    }
    HLD[i].push_front({b, k});
    
    for(; !st.empty(); st.pop()) {
        V.push_back(st.top());
    }
}

void solve(int x, int y) {
    for(y = C[y]; x;) {
        cut(head[x], depth[x] - depth[head[x]] + 1, y);
        x = up[head[x]];
    }
    cout << cnt_inv() << '\n';
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    edges.resize(n);
    for(int i = 1; i <= n;  ++ i) {
        cin >> edges[i - 1].first;
        edges[i - 1].second = i;
        sz[i] = 1;
    }
    sort(edges.begin(), edges.end());
    for(int i = 0, j = 1; i < n; ++ i) {
        j += (i && edges[i - 1].first < edges[i].first);
        C[edges[i].second] = j;
    }
    edges.pop_back();
    for(auto &[a, b] : edges) {
        cin >> a >> b;
        adj[a].push_back(b);
        up[b] = a;
        depth[b] = depth[a] + 1;
    }
    for(int i = n - 1; i --> 0;) {
        sz[edges[i].first] += sz[edges[i].second];
    }
    dfs(1);
    for(auto &[x, y] : edges) {
        solve(x, y);
    }
}

Compilation message (stderr)

construction.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main() {
      | ^~~~

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