Submission #943614

#	Time	Username	Problem	Language	Result	Execution time	Memory
943614		a_l_i_r_e_z_a	Untitled (POI11_rot)	C++17	100 / 100	177 ms	32460 KiB

Main

// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())

const ll maxn = 4e5 + 10;
const ll inf = 1e9 + 7;
ll n, nm, lc[maxn], rc[maxn], sz[maxn], a[maxn], nl[maxn], fen[maxn];
ll ans[maxn], res;
vector<ll> vec;

void input(ll v){
    sz[v] = 1;
    ll u; cin >> u;
    if(u){
        a[v] = u;
        nl[v] = 1;
        return;
    }
    lc[v] = ++nm;
    input(nm);
    sz[v] += sz[lc[v]];
    rc[v] = ++nm;
    input(nm);
    sz[v] += sz[rc[v]];
    nl[v] = nl[lc[v]] + nl[rc[v]];
}

ll get(ll i){
    ll rr = 0;
    for(; i; i &= i - 1) rr += fen[i];
    return rr;
}

void upd(ll i, ll x){
    for(; i <= n; i += i & -i) fen[i] += x;
}

void dfs2(ll v){
    if(lc[v] == -1){
        res += get(n) - get(a[v]);
        return;
    }
    dfs2(lc[v]);
    dfs2(rc[v]);
}

void dfs3(ll v){
    if(lc[v] == -1){
        upd(a[v], 1);
        vec.pb(a[v]);
        return;
    }
    dfs3(lc[v]);
    dfs3(rc[v]);
}

void reset(){
    for(auto u: vec) upd(u, -1);
    vec.clear();
}

void dfs(ll v){
    if(lc[v] == -1){
        upd(a[v], 1);
        vec.pb(a[v]);
        return;
    }
    if(sz[lc[v]] < sz[rc[v]]) swap(lc[v], rc[v]);
    dfs(rc[v]);
    reset();
    dfs(lc[v]);
    res = 0;
    ans[v] = ans[lc[v]] + ans[rc[v]];
    dfs2(rc[v]);
    ans[v] += min(nl[lc[v]] * nl[rc[v]] - res, res);
    dfs3(rc[v]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(ll i = 0; i <= 2 * n - 1; i++) lc[i] = rc[i] = -1;
    input(0);
    dfs(0);
    cout << ans[0] << '\n';

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10