oj.uz

Submission #612987

# Submission time Handle Problem Language Result Execution time Memory
612987 2022-07-30T02:42:34 Z 1bin Tree Rotations (POI11_rot) C++14
100 / 100
 233 ms 56840 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 4e5 + 5;
int n, t, a[NMAX], lc[NMAX], rc[NMAX], rt[NMAX];
int l[NMAX * 20], r[NMAX * 20], s[NMAX * 20], cnt;
ll ans, r1, r2;

void dfs(int x){
    cin >> a[x];
    if(!a[x]){
        lc[x] = ++t; dfs(lc[x]);
        rc[x] = ++t; dfs(rc[x]);
    }
    return;
}

int upd(int le, int ri, int k){
    int ix = ++cnt;
    s[ix] = 1;
    if(le == ri) return ix;
    int m = (le + ri) / 2;
    if(k <= m) l[ix] = upd(le, m, k);
    else r[ix] = upd(m + 1, ri, k);
    return ix;
}

int merge(int x, int y){
    if(!x) return y;
    if(!y) return x;
    r1 += 1LL * s[l[x]] * s[r[y]];
    r2 += 1LL * s[l[y]] * s[r[x]];
    l[x] = merge(l[x], l[y]);
    r[x] = merge(r[x], r[y]);
    s[x] = s[l[x]] + s[r[x]];
    return x;
}

ll dfs2(int x){
    if(a[x]) return 0;
    ll ret = dfs2(lc[x]) + dfs2(rc[x]);
    r1 = r2 = 0;
    rt[x] = merge(rt[lc[x]], rt[rc[x]]);
    ret += min(r1, r2);
    return ret;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    dfs(++t);
    
    for(int i = 1; i <= t; i++) 
        if(a[i]) rt[i] = upd(1, n, a[i]);
    cout << dfs2(1);
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 5 ms 1308 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3028 KB Output is correct
2 Correct 10 ms 2832 KB Output is correct
3 Correct 27 ms 6916 KB Output is correct
4 Correct 9 ms 3284 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11908 KB Output is correct
2 Correct 34 ms 11988 KB Output is correct
3 Correct 47 ms 13880 KB Output is correct
4 Correct 42 ms 14856 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 22820 KB Output is correct
2 Correct 81 ms 22100 KB Output is correct
3 Correct 112 ms 20784 KB Output is correct
4 Correct 78 ms 21136 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 29636 KB Output is correct
2 Correct 137 ms 29592 KB Output is correct
3 Correct 126 ms 31816 KB Output is correct
4 Correct 116 ms 31424 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 44844 KB Output is correct
2 Correct 151 ms 44496 KB Output is correct
3 Correct 197 ms 43492 KB Output is correct
4 Correct 151 ms 44012 KB Output is correct
5 Correct 163 ms 42516 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 48144 KB Output is correct
2 Correct 183 ms 52136 KB Output is correct
3 Correct 233 ms 52292 KB Output is correct
4 Correct 200 ms 54188 KB Output is correct
5 Correct 187 ms 50504 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 50380 KB Output is correct
2 Correct 230 ms 53328 KB Output is correct
3 Correct 176 ms 52160 KB Output is correct
4 Correct 206 ms 52276 KB Output is correct
5 Correct 221 ms 56840 KB Output is correct
6 Correct 170 ms 52116 KB Output is correct