Submission #705247

#	Time	Username	Problem	Language	Result	Execution time	Memory
705247		bebra	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 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
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccozKtHk.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKeFGNl.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status