Submission #1121178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121178		tab1540	Untitled (POI11_rot)	C++17	0 / 100	105 ms	65536 KiB

Main

#include <iostream>
#include <vector>

using namespace std;

struct sparseSeg {
    vector<pair<int, pair<int, int>>> segtre;
    
    sparseSeg() {
        segtre.push_back({0, {0, 0}});
    }

    void fix(int l, int r, int index) {
        if (l < r) {
            if (segtre[index].second.first == 0) {
                segtre[index].second.first = segtre.size();
                segtre.push_back({0, {0, 0}});
            }
            if (segtre[index].second.second == 0) {
                segtre[index].second.second = segtre.size();
                segtre.push_back({0, {0, 0}});
            }
        }
    }

    void update(int l, int r, int index, int tar, int val) {
        if (l == r) {
            segtre[index].first += val;
            return;
        }
        int mid = (l + r) >> 1;

        fix(l, r, index);

        if (tar <= mid) update(l, mid, segtre[index].second.first, tar, val);
        else update(mid + 1, r, segtre[index].second.second, tar, val);
        segtre[index].first = segtre[segtre[index].second.first].first + segtre[segtre[index].second.second].first;
    }

    int getSum(int l, int r, int index, int u, int v) {
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return segtre[index].first;

        int mid = (l + r) >> 1;

        int le = 0, ri = 0;
        if (segtre[index].second.first != 0) le = getSum(l, mid, segtre[index].second.first, u, v);
        if (segtre[index].second.second != 0) ri = getSum(mid + 1, r, segtre[index].second.second, u, v);

        return le + ri;
    }
};

sparseSeg ehe[400009];
vector<int> siz[400009];
int n;

int cur = 0;

unsigned long long ans = 0;

void dfs(int a) {
    int x;
    cin >> x;

    int e = cur;

    if (x == 0) {
        int le = ++cur;
        dfs(le);
        int ri = ++cur;
        dfs(ri);
        if (siz[le].size() < siz[ri].size()) {
            swap(le, ri);
        }

        unsigned long long ansFake = 0;

        for (int x : siz[ri]) {
            ansFake += ehe[le].getSum(1, n, 0, 1, x);
            siz[le].push_back(x);
        }

        ans += min(ansFake, (unsigned long long) siz[le].size() * siz[ri].size() - ansFake);

        for (int x : siz[ri]) {
            ehe[le].update(1, n, 0, x, 1);
        }

        swap(siz[e], siz[le]);
        swap(ehe[e], ehe[le]);
    } else {
        ehe[e].update(1, n, 0, x, 1);
        siz[e].push_back(x);   
    }
}

int main() {
    cin >> n;

    dfs(0);

    cout << ans;

    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10