Submission #564046

#	Time	Username	Problem	Language	Result	Execution time	Memory
564046		leeh18	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 KiB

bubblesort2

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

const int INF = 1e9;

struct lazy_segtree {
    int n;
    vector<int> tree, lazy;
    lazy_segtree(int n_) : n(n_), tree(4*n_, -INF), lazy(4*n_) {}
    void propagate(int node, int node_left, int node_right) {
        if (lazy[node] == 0) return;
        if (node_left != node_right) {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        tree[node] += lazy[node];
        lazy[node] = 0;
    }
    void update(int left, int right, int val, int node, int node_left, int node_right) {
        propagate(node, node_left, node_right);
        if (right < node_left || node_right < left) return;
        if (left <= node_left && node_right <= right) {
            lazy[node] = val;
            propagate(node, node_left, node_right);
            return;
        }
        int mid = (node_left + node_right) / 2;
        update(left, right, val, 2*node, node_left, mid);
        update(left, right, val, 2*node+1, mid+1, node_right);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }
    void update(int left, int right, int val) {
        update(left, right, val, 1, 0, n-1);
    }
    int query() {
        propagate(1, 0, n-1);
        return tree[1];
    }
    int query(int pos, int node, int node_left, int node_right) {
        propagate(1, 0, n-1);
        if (node_left == node_right) return tree[node];
        int mid = (node_left + node_right) / 2;
        if (pos <= mid) return query(pos, 2*node, node_left, mid);
        else return query(pos, 2*node+1, mid+1, node_right);
    }
    int query(int pos) {
        return query(pos, 1, 0, n-1);
    }
};

struct fenwick_tree {
    vector<int> tree;
    fenwick_tree(int n) : tree(n+1) {}
    int sum(int pos) {
        ++pos;
        int ret = 0;
        while (pos > 0) {
            ret += tree[pos];
            pos &= (pos - 1);
        }
        return ret;
    }
    void add(int pos, int val) {
        ++pos;
        while (pos < (int)tree.size()) {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<ll> v(N), c(N+Q);
    vector<pair<int, ll>> q(Q);
    for (int i = 0; i < N; i++) {
        cin >> v[i];
        v[i] = v[i] * N + i;
        c[i] = v[i];
    }
    for (int i = 0; i < Q; i++) {
        cin >> q[i].first >> q[i].second;
        q[i].second = q[i].second * N + q[i].first;
        c[N+i] = q[i].second;
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    fenwick_tree ft((int)c.size());
    for (int i = 0; i < N; i++) {
        auto it = lower_bound(c.begin(), c.end(), v[i]);
        v[i] = it - c.begin();
        ft.add(v[i], 1);
    }
    for (int i = 0; i < Q; i++) {
        auto it = lower_bound(c.begin(), c.end(), q[i].second);
        q[i].second = it - c.begin();
    }
    lazy_segtree seg((int)c.size() + 1);
    for (int i = 0; i < N; i++) {
        seg.update(v[i], v[i], i - ft.sum(v[i]-1) + INF);
    }
    for (auto [pos, val] : q) {
        seg.update(v[pos], v[pos], -INF - seg.query(v[pos]));
        ft.add(v[pos], -1);
        seg.update(v[pos]+1, (int)c.size() + 1, 1);
        v[pos] = val;
        ft.add(v[pos], 1);
        seg.update(v[pos]+1, (int)c.size() + 1, -1);
        seg.update(v[pos], v[pos], pos - ft.sum(v[pos]-1) - seg.query(v[pos]));
        cout << seg.query() << '\n';
    }
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc0YollJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4EmyoK.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc0YollJ.o: in function `main':
grader.cpp:(.text.startup+0x181): 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