Submission #636276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636276	2022-08-28T17:25:06 Z	jame0313	Tree Rotations (POI11_rot)	C++17	54 / 100	167 ms	65536 KB

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
int _cnt = 0;
int arr[400001];
struct segtree {
    vector<int> tree[(1 << 20) + 1];
    int siz;
    void init(int N) {
        for (siz = 1; siz < N; siz <<= 1)
            ;
        for (int i = 0; i < N; i++) {
            tree[siz + i] = {arr[i]};
        }
        for (int pos = siz - 1; pos; pos--) {
            tree[pos].reserve(tree[pos * 2].size() + tree[pos * 2 + 1].size());
            merge(tree[pos * 2].begin(), tree[pos * 2].end(),
                  tree[pos * 2 + 1].begin(), tree[pos * 2 + 1].end(),
                  back_inserter(tree[pos]));
        }
    }
    int sol(int l, int r, int s, int e, int pos, int v) {
        if (s <= l && r <= e)
            return upper_bound(tree[pos].begin(), tree[pos].end(), v) -
                   tree[pos].begin();
        if (e < l || r < s) return 0;
        return sol(l, (l + r) / 2, s, e, pos * 2, v) +
               sol((l + r) / 2 + 1, r, s, e, pos * 2 + 1, v);
    }
    int sol(int s, int e, int v) { return sol(0, siz - 1, s, e, 1, v); }
} tree;
int in[400001];
int out[400001];
int psum[400001];
vector<vector<int> > mp;
int id = -1;
int parse(int x) {
    int c;
    cin >> c;
    in[x] = x;
    if (c == 0) {
        int l = parse(++id);
        int r = parse(++id);
        mp[x].push_back(l);
        mp[x].push_back(r);
    } else {
        arr[x] = c;
    }
    out[x] = id;
    return in[x];
}
ll sol(int x) {
    ll ret = 0;
    if (arr[x] == 0) {
        int a = mp[x][0];
        int b = mp[x][1];
        ret += sol(a) + sol(b);
        if (out[a] - in[a] < out[b] - in[b]) swap(a, b);
        ll acnt = 0, bcnt = 0;
        int zero_cnt = psum[out[a]] - psum[in[a]] + (arr[in[a]] == 0);
        int siz = out[a] - in[a] + 1 - zero_cnt;
        for (int i = in[b]; i <= out[b]; i++) {
            if (!arr[i]) continue;
            int cnt = tree.sol(in[a], out[a], arr[i] - 1) - zero_cnt;
            // cout<<cnt<<endl;
            acnt += cnt;
            bcnt += siz - cnt;
        }
        ret += min(acnt, bcnt);
        return ret;

    } else {
        return 0;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    mp.resize(2 * N + 1);
    int r = parse(++id);
    psum[0] = arr[0] == 0;
    for (int i = 1; i <= id; i++) psum[i] = psum[i - 1] + (arr[i] == 0);
    tree.init(id + 1);
    cout << sol(r);
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	24916 KB	Output is correct
2	Correct	17 ms	24916 KB	Output is correct
3	Correct	14 ms	24948 KB	Output is correct
4	Correct	14 ms	24916 KB	Output is correct
5	Correct	14 ms	24952 KB	Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	25132 KB	Output is correct
2	Correct	14 ms	25160 KB	Output is correct
3	Correct	15 ms	25168 KB	Output is correct
4	Correct	14 ms	25280 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	26648 KB	Output is correct
2	Correct	20 ms	26324 KB	Output is correct
3	Correct	19 ms	26872 KB	Output is correct
4	Correct	19 ms	26976 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	30548 KB	Output is correct
2	Correct	39 ms	29088 KB	Output is correct
3	Correct	106 ms	35112 KB	Output is correct
4	Correct	33 ms	30548 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	167 ms	42616 KB	Output is correct
2	Correct	112 ms	45192 KB	Output is correct
3	Correct	138 ms	49568 KB	Output is correct
4	Correct	114 ms	50332 KB	Output is correct

Subtask #7
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	80 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	91 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	83 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	87 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	78 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #636276

Compilation message