Submission #1066841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066841		vux2code	Untitled (POI11_rot)	C++17	36 / 100	1084 ms	60172 KiB

Main

// Src : Vux2Code
/* Note : 1
    none
*/

#include <bits/stdc++.h>

using namespace std;

template <typename T> void vout(T s){ cout << s << endl; exit(0);}

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

const ll maxN = 1e6 + 5, maxLog = 20, inf64 = 1e18, mod = 1e9 + 7;

ll t = 1;

struct Node {
    ll child [2], pr, cnt, l, r;
    bool en;
    Node () {child [0] = 0; child [1] = 0; pr = 0; en = false; cnt = 0; l = 0; r = 0;}
};

ll n, pos, posCnt, tmp, root, cnt, a [maxN];
Node node [maxN]; 

ll build (ll x) {
    if (x <= n) {
        //cerr << x << ' ' << cnt << '\n';
        node [x]. l = cnt;
        node [x]. r = cnt;
        a [cnt] = x;
        cnt ++;
        return 0;
    }
    ll ans = 0;
    ans += build (node [x]. child [0]);
    ans += build (node [x]. child [1]);
    node [x]. l = node [node [x]. child [0]]. l;
    node [x]. r = node [node [x]. child [1]]. r;
    ll tmp1 = node [x]. child [0];
    ll tmp2 = node [x]. child [1];
    ll j = node [tmp2]. l; 
    ll ans1 = 0, ans2 = 0;
    for (ll i = node [tmp1]. l; i <= node [tmp1]. r; i ++) {
        while (j <= node [tmp2]. r && a [j] < a [i]) j ++;
        ans1 += j - node [tmp2]. l; 
        ans2 += node [tmp2]. r - j + 1;
    }
    sort (a + node [x]. l, a + node [x]. r + 1);
    ans += min (ans1, ans2);
    return ans;    
}

void solve () {
    cin >> n;
    root = posCnt;
    posCnt = n + 1;
    pos = posCnt;
    cin >> tmp;
    while (cin >> tmp) {
        if (tmp) {
            node [tmp]. en = true;
            if (node [pos]. child [0] == 0) {
                node [pos]. child [0] = tmp;
            }
            else node [pos]. child [1] = tmp;
            while (node [pos]. child [1]) {
                pos = node [pos]. pr;
            }
        }
        else {
            posCnt ++;
            if (node [pos]. child [0] == 0) {
                node [pos]. child [0] = posCnt;
            }
            else node [pos]. child [1] = posCnt;
            node [posCnt]. pr = pos;
            pos = posCnt;
        }
        // cerr << pos << ' ';
    }
    // cerr << '\n';
    cout << build (n + 1);
    // for (int i = 0; i <= cnt; i ++) cerr << a [i] << ' ';
    // cerr << '\n';
    // for (int i = 1; i <= posCnt; i ++) cerr << node [i]. l << ' ' << node [i]. r << '\n';
}

int main () {
    ios::sync_with_stdio (0);
    cin. tie (0);
    cout. tie (0);
    // #define TASK "task"
    // freopen (TASK".inp", "r", stdin);
    // freopen (TASK".out", "w", stdout);
    // cin >> t;
    while (t --) solve ();
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 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