Submission #711672

#	Time	Username	Problem	Language	Result	Execution time	Memory
711672		Cyanmond	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	251 ms	4104 KiB

bubblesort2

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

constexpr int inf = 1 << 25;

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;
    }
};

using T = std::pair<int, int>;
struct kDTree {
    int xMn, xMx, yMn, yMx;
    int val, lazy;
    kDTree *l = nullptr, *r = nullptr;
    kDTree(std::vector<T> &vec, bool divx) {
        val = lazy = 0;
        xMn = yMn = inf, xMx = yMx = -inf;
        const int n = (int)vec.size();
        for (int i = 0; i < n; ++i) {
            const auto &[x, y] = vec[i];
            xMn = std::min(xMn, x);
            xMx = std::max(xMx, x);
            yMn = std::min(yMn, y);
            yMx = std::max(yMx, y);
        }
        if (n == 1) return;
        const int m = n / 2;
        if (divx) {
            std::nth_element(vec.begin(), vec.begin() + m, vec.end(), [&](const auto &a, const auto &b) {
                return a.first < b.first;
            });
        } else {
            std::nth_element(vec.begin(), vec.begin() + m, vec.end(), [&](const auto &a, const auto &b) {
                return a.second < b.second;
            });
        }
        std::vector<T> lVec, rVec;
        std::copy(vec.begin(), vec.begin() + m, std::back_inserter(lVec));
        std::copy(vec.begin() + m, vec.end(), std::back_inserter(rVec));
        l = new kDTree(lVec, not divx);
        r = new kDTree(rVec, not divx);
    }

    void all_apply(int f) {
        val += f;
        lazy += f;
    }

    void push() {
        if (l != nullptr) l->all_apply(lazy);
        if (r != nullptr) r->all_apply(lazy);
        lazy = 0;
    }

    void add(int x1, int x2, int y1, int y2, int v) {
        push();
        if (x2 < xMn or x1 > xMx or y2 < yMn or y1 > yMx) return;
        if (x1 <= xMn and xMx <= x2 and y1 <= yMn and yMx <= y2) {
            all_apply(v);
            return;
        }
        l->add(x1, x2, y1, y2, v);
        r->add(x1, x2, y1, y2, v);
        if (l != nullptr) val = std::max(val, l->val);
        if (r != nullptr) val = std::max(val, r->val);
    }

    int calc(int x1, int x2, int y1, int y2) {
        push();
        if (x2 < xMn or x1 > xMx or y2 < yMn or y1 > yMx) return 0;
        if (x1 <= xMn and xMx <= x2 and y1 <= yMn and yMx <= y2) {
            return val;
        }
        return std::max(l->calc(x1, x2, y1, y2), r->calc(x1, x2, y1, y2));
    }
};

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());
    }
    std::vector<T> vec;
    for (int i = 0; i < N; ++i) {
        vec.push_back({i, A[i]});
    }
    for (int i = 0; i < Q; ++i) {
        vec.push_back({X[i], V[i]});
    }
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    kDTree tree(vec, true);
    for (const auto &[x, y] : vec) tree.add(x, x, y, y, -inf);
    for (int i = 0; i < N; ++i) {
        tree.add(i, i, A[i], A[i], inf);
        tree.add(i + 1, N - 1, 0, A[i] - 1, 1);
    }
    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];
        tree.add(x + 1, N - 1, 0, preVal - 1, -1);
        tree.add(x + 1, N - 1, 0, newVal - 1, 1);
        tree.add(x, x, preVal, preVal, -inf);
        tree.add(x, x, newVal, newVal, inf);
        answer[q] = tree.calc(0, N - 1, 0, inf);
    }
    return answer;
}

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