oj.uz

답안 #1066841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1039 ms 56148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1056 ms 60172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1084 ms 56660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1025 ms 59476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1060 ms 57848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1045 ms 57680 KB Time limit exceeded
2 Halted 0 ms 0 KB -