Submission #1323506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323506		chithanhnguyen	Bubble Sort 2 (JOI18_bubblesort2)	C++20	Compilation error	0 ms	0 KiB

bubblesort2

/*
Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528)
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

struct Normalize {
    vector<int> vals;

    void add(int v) {vals.push_back(v);}

    void build() {
        sort(all(vals));
        vals.erase(unique(all(vals)), end(vals));
    }

    int compress(int v) {
        return (int)(lower_bound(all(vals), v) - begin(vals)) + 1;
    }
};

struct FenwickTree {
    int n;
    vector<int> fen;

    FenwickTree(int _n) : n(_n), fen(n + 5, 0) {}

    void reset() {fill(all(fen), 0);}

    void update(int idx, int v) {
        for (int i = idx; i <= n; i += i & -i)
            fen[i] += v;
    }

    int get(int idx) {
        int sum = 0;
        for (int i = idx; i; i -= i & -i)
            sum += fen[i];
        return sum;
    }
};

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
    int n = (int)a.size(), q = (int)x.size();

    // Compressing the values
    Normalize norm;
    {
        for (auto val : a) norm.add(val);
        for (auto val : v) norm.add(val);

        norm.build();
        for (int i = 0; i < n; ++i) a[i] = norm.compress(a[i]);
        for (int i = 0; i < q; ++i) v[i] = norm.compress(v[i]);
    }

    vector<int> res(q, 0);

    int sz = (int)norm.vals.size() + 5;
    FenwickTree fen(sz);
    for (int i = 0; i < q; ++i) {
        fen.reset();
        a[x[i]] = v[i];
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int contrib = fen.get(sz) - fen.get(a[j]);
            fen.update(a[j], 1);
            ans = max(ans, contrib);
        }
        res[i] = ans;
    }

    return res;
}

#ifdef NCTHANH
signed main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> a(n), x(q), v(q);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < q; ++i)
        cin >> x[i] >> v[i];

    vector<int> res = countScans(a, x, v);
    for (int i = 0; i < q; ++i) cout << res[i] << '\n'; 
    
    return 0;
}
#endif

Compilation message (stderr)

/usr/bin/ld: /tmp/cc3mF8o5.o: in function `main':
grader.cpp:(.text.startup+0x189): undefined reference to `countScans(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status