Submission #705455

#	Time	Username	Problem	Language	Result	Execution time	Memory
705455		bebra	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3205 ms	157080 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;
    }
};


const int INF = 1e9;

struct SegmentTree {
    struct Node {
        int value;
        int push;

        Node(int _value = -INF, int _push = 0)
            : value(_value), push(_push) {}

        friend Node combine(const Node& lhs, const Node& rhs) {
            return {max(lhs.value, rhs.value), 0};
        }
    };

    vector<Node> tree;
    int size;

    SegmentTree(int n) {
        size = 1 << (__lg(n) + 1);
        tree.resize(2 * size - 1);
    }

    void point_update(int pos, int value) {
        point_update(0, size, 0, pos, value);
    }

    void point_update(int l, int r, int v, int pos, int value) {
        push(l, r, v);
        if (l == r - 1) {
            tree[v].value = value;
            return;
        }
        int m = (l + r) / 2;
        if (pos < m) {
            point_update(l, m, 2 * v + 1, pos, value);
        } else {
            point_update(m, r, 2 * v + 2, pos, value);
        }
        tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update(int lq, int rq, int value) {
        update(0, size, 0, lq, rq, value);
    }

    void apply(int v, int value) {
        tree[v].value += value;
        tree[v].push += value;
    }

    void push(int l, int r, int v) {
        if (l == r - 1 || tree[v].push == 0) return;
        apply(2 * v + 1, tree[v].push);
        apply(2 * v + 2, tree[v].push);
        tree[v].push = 0;
    }

    void update(int l, int r, int v, int lq, int rq, int value) {
        push(l, r, v);
        if (lq <= l && r <= rq) {
            apply(v, value);
            return;
        } else if (l >= rq || r <= lq) {
            return;
        }
        int m = (l + r) / 2;
        update(l, m, 2 * v + 1, lq, rq, value);
        update(m, r, 2 * v + 2, lq, rq, value);
        tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
    }

    int get_max() const {
        return tree[0].value;
    }
};



vector<int> countScans(vector<int> a, vector<int> pos, vector<int> value){
    int n = a.size();
	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];
    }

    FenwickTree tree(k);
    for (auto x : a) {
        tree.update(x, 1);
    }

    SegmentTree segtree(k);
    vector<set<int, greater<int>>> occurs(k);
    for (int i = 0; i < n; ++i) {
        segtree.point_update(a[i], i - tree.query(0, a[i]) + 1);
        occurs[a[i]].insert(i);
    }

    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        {
            int x = a[pos[i]];
            
            tree.update(x, -1);
            occurs[x].erase(pos[i]);

            segtree.update(x, k, 1);
            
            if (occurs[x].empty()) {
                segtree.point_update(x, -INF);
            } else {
                int new_value = *occurs[x].begin() - tree.query(0, x) + 1;
                segtree.point_update(x, new_value);
            }
        }

        {
            int x = value[i];
            a[pos[i]] = x;

            occurs[x].insert(pos[i]);
            tree.update(x, 1);

            int new_value = *occurs[x].begin() - tree.query(0, x) + 1;

            segtree.update(x, k, -1);
            segtree.point_update(x, new_value);
        }

        ans[i] = segtree.get_max();
    }

	return ans;
}

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