Submission #705249

#	Time	Username	Problem	Language	Result	Execution time	Memory
705249		bebra	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9064 ms	1620 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


struct FenwickTree {
    vector<int> tree;
    int size;

    FenwickTree(int n) {
        size = n;
        tree.resize(size);
    }

    void update(int pos, int value) {
        for (int i = pos; i < size; i |= i + 1) {
            tree[i] += value;
        }
    }

    int query(int l, int r) {
        int res = 0;
        for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
            res += tree[i];
        }
        for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
            res -= tree[i];
        }
        return res;
    }
};




vector<int> countScans(vector<int> a, vector<int> pos, vector<int> value){
	int q = pos.size();

    vector<int> all_values = a;
    all_values.insert(all_values.end(), value.begin(), value.end());


    sort(all_values.begin(), all_values.end());
    all_values.resize(unique(all_values.begin(), all_values.end()) - all_values.begin());

    int k = all_values.size();
    map<int, int> mp;
    for (int i = 0; i < k; ++i) {
        mp[all_values[i]] = i;
    }

    for (auto& x : a) {
        x = mp[x];
    }
    for (auto& x : value) {
        x = mp[x];
    }

    auto count = [&]() -> int {
        // the answer is maximum number of inversions for a single number
        FenwickTree tree(k);
        // maybe will be better to reverse the array for simplicity
        int res = 0;
        for (auto x : a) {
            res = max(res, tree.query(x + 1, k - 1));
            tree.update(x, 1);
        }
        return res;
    };

    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        a[pos[i]] = value[i];
        ans[i] = count();
    }

	return ans;
}



// int main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int n, q;
//     cin >> n >> q;
//     vector<int> a(n);
//     for (auto& x : a) {
//         cin >> x;
//     }
//     vector<int> pos(q), value(q);
//     for (int i = 0; i < q; ++i) {
//         cin >> pos[i] >> value[i];
//     }
//     for (auto x : countScans(a, pos, value)) {
//         cout << x << '\n';
//     }
//     return 0;
// }


/*
4 2
1 2 3 4
0 3
2 1
*/

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40