oj.uz

Submission #1066905

# Submission time Handle Problem Language Result Execution time Memory
1066905 2024-08-20T08:39:05 Z vux2code Tree Rotations (POI11_rot) C++17
0 / 100
 1000 ms 62572 KB 
// 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], b [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, fk = node [x]. l;
    for (ll i = node [tmp1]. l; i <= node [tmp1]. r; i ++) {
        while (j <= node [tmp2]. r && a [j] < a [i]) {
            b [fk ++] = a [j];
            j ++;
        }
        b [fk ++] = a [i];
        ans1 += j - node [tmp2]. l; 
        ans2 += node [tmp2]. r - j + 1;
    }
    for (int i = node [x]. l; i <= node [x]. r; i ++) a [i] = b [i];
    // 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 55128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 55124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 55128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 55524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 56268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 56408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 62572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 57936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 904 ms 62056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 59624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 59696 KB Time limit exceeded
2 Halted 0 ms 0 KB -