Submission #1066841

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1066841	2024-08-20T08:00:05 Z	vux2code	Tree Rotations (POI11_rot)	C++17	36 / 100	1000 ms	60172 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];
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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	55132 KB	Output is correct
2	Correct	21 ms	55132 KB	Output is correct
3	Correct	27 ms	55260 KB	Output is correct
4	Correct	23 ms	55096 KB	Output is correct
5	Correct	22 ms	55128 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	55108 KB	Output is correct
2	Correct	19 ms	55132 KB	Output is correct
3	Correct	19 ms	55096 KB	Output is correct
4	Correct	19 ms	55176 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	55260 KB	Output is correct
2	Correct	20 ms	55132 KB	Output is correct
3	Correct	20 ms	55264 KB	Output is correct
4	Correct	20 ms	55132 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	55388 KB	Output is correct
2	Correct	24 ms	55132 KB	Output is correct
3	Correct	127 ms	55268 KB	Output is correct
4	Correct	73 ms	55384 KB	Output is correct

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	55892 KB	Output is correct
2	Execution timed out	1042 ms	56656 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1060 ms	57848 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	1045 ms	57680 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #1066841

Compilation message