Submission #711522

#	Time	Username	Problem	Language	Result	Execution time	Memory
711522		Cyanmond	Bubble Sort 2 (JOI18_bubblesort2)	C++17	22 / 100	1035 ms	56632 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

constexpr int inf = 1 << 30;

class SegTree {
    int n, size;
    std::vector<int> data;
    public:
    SegTree() {}
    SegTree(const std::vector<int> &vec) {
        n = (int)vec.size();
        size = 1;
        while (size < n) size *= 2;
        data.assign(2 * size, 0);
        std::copy(vec.begin(), vec.end(), data.begin() + size);
        for (int i = size - 1; i >= 1; --i) data[i] = data[2 * i] + data[2 * i + 1];
    }

    void set(int i, int v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            data[i] = data[2 * i] + data[2 * i + 1];
        }
    }

    int fold(int l, int r) {
        int ret = 0;
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l & 1) ret += data[l++];
            if (r & 1) ret += data[--r];
        }
        return ret;
    }
};

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
    const int N = (int)A.size(), Q = (int)X.size();
    {
        std::vector<int> vals;
        std::copy(A.begin(), A.end(), std::back_inserter(vals));
        std::copy(V.begin(), V.end(), std::back_inserter(vals));
        std::sort(vals.begin(), vals.end());
        vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
        for (auto &e : A) e = (int)(std::lower_bound(vals.begin(), vals.end(), e) - vals.begin());
        for (auto &e : V) e = (int)(std::lower_bound(vals.begin(), vals.end(), e) - vals.begin());
    }
    // subtask 3
    const int M =
        std::max(*std::max_element(A.begin(), A.end()), *std::max_element(V.begin(), V.end())) + 1;
    assert(M <= 100);
    std::vector<SegTree> seg(M + 1);
    std::vector<std::set<int>> ids(M);
    for (int x = 0; x <= M; ++x) {
        std::vector<int> vec(N);
        for (int i = 0; i < N; ++i) {
            if (A[i] < x) {
                vec[i] = 1;
            }
            if (A[i] == x) {
                ids[x].insert(i);
            }
        }
        seg[x] = SegTree(vec);
    }

    std::vector<int> answer(Q);
    for (int q = 0; q < Q; ++q) {
        const int x = X[q], newVal = V[q];
        const int preVal = A[x];
        ids[preVal].erase(x);
        ids[newVal].insert(x);
        for (int v = preVal + 1; v <= M; ++v) {
            seg[v].set(x, 0);
        }
        for (int v = newVal + 1; v <= M; ++v) {
            seg[v].set(x, 1);
        }
        A[x] = newVal;
        for (int v = 0; v < M; ++v) {
            if (ids[v].empty()) continue;
            const int i = *ids[v].rbegin();
            answer[q] = std::max(answer[q], i - seg[v + 1].fold(0, i));
        }
    }
    return answer;
}

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