Submission #636276

#	Time	Username	Problem	Language	Result	Execution time	Memory
636276		jame0313	Untitled (POI11_rot)	C++17	54 / 100	167 ms	65536 KiB

Main

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10