Submission #862140

#	Time	Username	Problem	Language	Result	Execution time	Memory
862140		vjudge1	Untitled (POI11_rot)	C++17	0 / 100	1037 ms	33632 KiB

Main

// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define int long long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,mid
#define TR v+v+1,mid+1,tr

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;

int binpow(int a,int n,int M) {
    if (n==0)
        return 1;
    if (n%2!=0)
        return (a * binpow(a,n-1,M))%M;
    int z=binpow(a,n/2,M);
    return (z*z)%M;
}

const ll INF = 1e18;
const int N =  2e5+7;
const int M = 1e9+7;
const ll HZ = 1e5;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;

int n,l[N],r[N],t=1,a[N],sz[N],ans[N];
vector <int> d[2];
vector <vector <int>> g(2,vector <int> (N));

void upd(int v,int tl,int tr,int pos,int dir) {
    if (tl==tr) {
        g[dir][v]++;
        return;
    }
    if (pos<=md)
        upd(v+v,tl,md,pos,dir);
    else
        upd(v+v+1,md+1,tr,pos,dir);
    g[dir][v]=g[dir][v+v],g[dir][v+v+1];
}

int get(int v,int tl,int tr,int l,int r,int dir) {
    if (tl>=l and tr<=r)
        return g[dir][v];
    if (tl>r or tr<l)
        return 0;
    return get(v+v,tl,md,l,r,dir)+get(v+v+1,md+1,tr,l,r,dir);
}

void read(int v) {
    int z;
    cin >> z;
    sz[v]=1;
    if (z) {
        a[v]=z;
        return;
    }
    l[v]=++t;
    read(t);
    sz[v]+=sz[l[v]];
    r[v]=++t;
    read(t);
    sz[v]+=sz[r[v]];
}

int calc1(int v, bool rev) {
    int x=0;
    for (auto now : d[0]) {
        if (!rev) {
            if (now>1)
                x += get(1, 1, n, 1, now - 1,1);
        } else {
            if (now<n)
                x += get(1, 1, n, now+1, n,1);
        }
    }
    return x;
}

int calc2(int v, bool rev) {
    int x=0;
    for (auto now : d[1]) {
        if (rev) {
            if (now>1)
                x += get(1, 1, n, 1, now - 1,0);
        } else {
            if (now<n)
                x += get(1, 1, n, now+1, n,0);
        }
    }
    return x;
}

void get(int v,int dir) {
    if (a[v]) {
        d[dir]={a[v]};
        upd(1,1,n,a[v],dir);
        ans[v]=0;
        return;
    }
    get(l[v],0), get(r[v],1);
    int L, R;
    if (sz[l[v]]>=sz[r[v]]) {
        L=calc1(v,false), R=calc1(v,true);
    } else {
        L=calc2(v,false), R=calc2(v,true);
    }
    ans[v]+=min(L,R);
    ans[v]+=ans[l[v]]+ans[r[v]];
    if (v==1)
        return;
    if (d[0].size()<d[1].size())
        d[0].swap(d[1]), g[0].swap(g[1]);
    for (auto now : d[1])
        d[0].push_back(now), upd(1,1,n,now,0);
    d[dir].swap(d[0]), g[dir].swap(g[0]);
}

void solve() {
    cin >> n;
    read(1);
    get(1,0);
    cout << ans[1];
}

signed main() {
    // freopen("lca.in", "r", stdin);
    // freopen("lca.out", "w", stdout);
    kanagattandirilmagandiktarinizdan
    int test = 1,count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test) {
            cout << '\n';
        }
        count++;
    }
    return 0;
}//

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