oj.uz

답안 #1121251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -