Submission #999916

#	Time	Username	Problem	Language	Result	Execution time	Memory
999916		vjudge1	Construction of Highway (JOI18_construction)	C++17	16 / 100	96 ms	1040 KiB

construction

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"

using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 4005;
ll t[N];
void upd(ll v)
{
    for (; v < N; v |= (v + 1)) t[v]++;
}
ll sum(ll v)
{
    ll ans = 0;
    for (; v >= 0; v = (v & (v + 1)) - 1) ans += t[v];
    return ans;
}
ll c[N], p[N];
void solve()
{
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> c[i];
    {
        map<ll, ll> mp;
        for (ll i = 1; i <= n; i++) mp[c[i]] = 1;
        ll cur = 1;
        for (auto i : mp)
            mp[i.first] = cur++;
        for (ll i = 1; i <= n; i++) c[i] = mp[c[i]];
    }
    for (ll i = 1; i < n; i++)
    {
        ll a, b;
        cin >> a >> b;
        for (ll j = 0; j < N; j++) t[j] = 0;
        p[b] = a;
        ll v = a;
        ll ans = 0;
        while (v) ans += sum(c[v] - 1), upd(c[v]), v = p[v];
        v = b;
        while (v) c[v] = c[b], v = p[v];
        cout << ans << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    //cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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