oj.uz

Submission #119531

# Submission time Handle Problem Language Result Execution time Memory
119531 2019-06-21T10:59:14 Z popovicirobert Tree Rotations (POI11_rot) C++14
100 / 100
 212 ms 15988 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

/*
const int MOD = ;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}
*/

using namespace std;

//ifstream fin("B.in");
//ofstream fout("B.out");

const int MAXN = (int) 4e5;

int idl[MAXN + 1], idr[MAXN + 1], sz;
int son[MAXN + 1][2], arr[MAXN + 1];

int read(int &id) {
    int x, root = id;
    cin >> x;

    if(x == 0) {
        int a = read(++id), b = read(++id);
        son[root][0] = a, son[root][1] = b;
        idl[root] = idl[a], idr[root] = idr[b];
    }
    else {
        idl[root] = idr[root] = ++sz;
        arr[sz] = x;
    }

    return root;
}

int aib[MAXN + 1], n;

inline void update(int pos, int val) {
    for(int i = pos; i <= n; i += lsb(i)) {
        aib[i] += val;
    }
}

inline int query(int pos) {
    int ans = 0;
    for(int i = pos; i > 0; i -= lsb(i)) {
        ans += aib[i];
    }
    return ans;
}

vector <int> stk;
bool vis[MAXN + 1];
ll tot;

void dfs(int nod) {

    vis[nod] = 1;

    int a = son[nod][0], b = son[nod][1];
    if(idr[b] - idl[b] > idr[a] - idl[a]) {
        swap(a, b);
    }

    if(a == 0 && b == 0) {
        update(arr[idl[nod]], 1);
        stk.push_back(arr[idl[nod]]);
        return ;
    }

    dfs(a);

    ll cur = 0;
    for(int i = idl[b]; i <= idr[b]; i++) {
        cur += query(n) - query(arr[i]);
    }
    for(int i = idl[b]; i <= idr[b]; i++) {
        update(arr[i], 1);
        stk.push_back(arr[i]);
    }

    tot += min(cur, 1LL * (idr[a] - idl[a] + 1) * (idr[b] - idl[b] + 1) - cur);

}

int main() {
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    int id = 1;
    int root = read(id);

    for(i = 1; i <= id; i++) {
        if(vis[i]) {
            continue;
        }
        dfs(i);

        for(auto it : stk) {
            update(it, -1);
        }

        stk.clear();
    }

    cout << tot;

    //fin.close();
    //fout.close();
    return 0;
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:111:9: warning: unused variable 'root' [-Wunused-variable]
     int root = read(id);
         ^~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 22 ms 2120 KB Output is correct
4 Correct 7 ms 1408 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2816 KB Output is correct
2 Correct 23 ms 3840 KB Output is correct
3 Correct 25 ms 4736 KB Output is correct
4 Correct 26 ms 4864 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7680 KB Output is correct
2 Correct 38 ms 6904 KB Output is correct
3 Correct 43 ms 6032 KB Output is correct
4 Correct 41 ms 5368 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5876 KB Output is correct
2 Correct 49 ms 7672 KB Output is correct
3 Correct 51 ms 9332 KB Output is correct
4 Correct 49 ms 9328 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 10100 KB Output is correct
2 Correct 89 ms 10696 KB Output is correct
3 Correct 82 ms 10868 KB Output is correct
4 Correct 91 ms 10228 KB Output is correct
5 Correct 151 ms 9660 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 9332 KB Output is correct
2 Correct 92 ms 14572 KB Output is correct
3 Correct 108 ms 13684 KB Output is correct
4 Correct 83 ms 15220 KB Output is correct
5 Correct 191 ms 10936 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9400 KB Output is correct
2 Correct 97 ms 12420 KB Output is correct
3 Correct 142 ms 11212 KB Output is correct
4 Correct 109 ms 11220 KB Output is correct
5 Correct 103 ms 15988 KB Output is correct
6 Correct 212 ms 11292 KB Output is correct