Submission #1121251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1121251	2024-11-28T15:59:30 Z	tab1540	Tree Rotations (POI11_rot)	C++17	72 / 100	749 ms	65536 KB

#include <iostream>
#include <vector>
#include <map>

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;
    }
};

map<int, sparseSeg> ehe;
vector<vector<int>> siz;
int n;

int cur = 0;

unsigned long long ans = 0;

void dfs(int a) {
    siz.push_back(vector<int>());
    int x;
    cin >> x;

    int e = cur;

    ehe[e] = sparseSeg();

    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);
        }

        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);
            siz[le].push_back(x);
        }

        swap(siz[e], siz[le]); siz[ri].clear();

        swap(ehe[e], ehe[le]);  ehe.erase(ehe.find(ri)); ehe.erase(ehe.find(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
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	2716 KB	Output is correct
2	Correct	13 ms	1360 KB	Output is correct
3	Correct	8 ms	2896 KB	Output is correct
4	Correct	8 ms	3152 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	7776 KB	Output is correct
2	Correct	33 ms	2940 KB	Output is correct
3	Correct	106 ms	6872 KB	Output is correct
4	Correct	37 ms	6440 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	184 ms	11448 KB	Output is correct
2	Correct	139 ms	22264 KB	Output is correct
3	Correct	160 ms	33524 KB	Output is correct
4	Correct	164 ms	31736 KB	Output is correct

Subtask #7
0 / 9.0

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

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	266 ms	26164 KB	Output is correct
2	Correct	260 ms	42472 KB	Output is correct
3	Correct	299 ms	61672 KB	Output is correct
4	Correct	290 ms	62952 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	731 ms	57676 KB	Output is correct
2	Correct	462 ms	40908 KB	Output is correct
3	Correct	540 ms	57744 KB	Output is correct
4	Correct	537 ms	44940 KB	Output is correct
5	Correct	749 ms	40424 KB	Output is correct

Subtask #10
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	590 ms	58228 KB	Output is correct
2	Runtime error	140 ms	65536 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	704 ms	47576 KB	Output is correct
2	Runtime error	338 ms	65536 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Submission #1121251

Compilation message