Submission #338612

#	Time	Username	Problem	Language	Result	Execution time	Memory
338612		KoD	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	26 ms	1516 KiB

bubblesort2

#include <bits/stdc++.h>
 
template <class T>
using Vec = std::vector<T>;

constexpr int INF = 1000000000;

struct Mn {
    int value;
    static Mn id() {
        return Mn { -INF };
    }
    Mn operator + (const Mn &other) const {
        return Mn { std::max(value, other.value) };
    }
};

struct Ef {
    int add;
    static Ef id() {
        return Ef { 0 };
    }
    Ef operator + (const Ef &other) const {
        return Ef { add + other.add };
    }
};

Mn operator * (const Mn &m, const Ef &e) {
    return m.value == -INF ? m : Mn { m.value + e.add };
}

struct Segtree {
    struct Node {
        Mn m;
        Ef e;
    };

    int size;
    Vec<Node> data;

    Segtree(const int n) {
        for (size = 1; size < n; size <<= 1);
        data.resize(2 * size, Node { Mn::id(), Ef::id() });
    }
    
    static int bit_lsb(const int x) {
        return __builtin_ctz(x);
    }
    static int bit_width(const int x) {
        return 32 - __builtin_clz(x);
    }

    void apply(const int k, const Ef &e) {
        data[k].m = data[k].m * e;
        data[k].e = data[k].e + e;
    }
    void fetch(const int k) {
        data[k].m = data[k << 1 | 0].m + data[k << 1 | 1].m;
    }
    void flush(const int k) {
        apply(k << 1 | 0, data[k].e);
        apply(k << 1 | 1, data[k].e);
        data[k].e = Ef::id();
    }

    void push(const int k) {
        const int lsb = bit_lsb(k);
        for (int d = bit_width(k); d != lsb; --d) {
            flush(k >> d);
        }
    }
    void pull(int k) {
        k >>= bit_lsb(k);
        while (k > 1) {
            k >>= 1;
            fetch(k);
        }
    }

    void operate(int l, int r, int x) {
        l += size;
        r += size;
        const auto lc = l;
        const auto rc = r;
        push(l);
        push(r);
        const Ef e { x };
        while (l < r) {
            if (l & 1) {
                apply(l, e);
                l += 1;
            }
            l >>= 1;
            if (r & 1) {
                r -= 1;
                apply(r, e);
            }
            r >>= 1;
        }
        pull(l);
        pull(r);
    }

    void assign(int i, int x) {
        i += size;
        push(i);
        push(i + 1);
        data[i].m = Mn { x };
        pull(i);
        pull(i + 1);
    }

    int fold() const {
        return data[1].m.value;
    }

    int fold(int l, int r) {
        l += size;
        r += size;
        push(l);
        push(r);
        Mn ret = Mn::id();
        while (l < r) {
            if (l & 1) {
                ret = ret + data[l].m;
                l += 1;
            }
            l >>= 1;
            if (r & 1) {
                r -= 1;
                ret = ret + data[r].m;
            }
            r >>= 1;
        }
        return ret.value;
    }
};

struct Fenwick {
    Vec<int> data;
    Fenwick(const int n): data(n + 1) { }

    void add(int i, int x) {
        for (i += 1; i < (int) data.size(); i += i & -i) {
            data[i] += x;
        }
    }

    int get(int i) {
        int ret = 0;
        for (; i > 0; i -= i & -i) {
            ret += data[i];
        }
        return ret;
    }
};

Vec<int> countScans(Vec<int> A, Vec<int> X, Vec<int> V) {
    const int N = A.size();
    const int Q = X.size();
    Vec<std::pair<int, int>> cmp;
    cmp.reserve(N + Q);
    for (int i = 0; i < N; ++i) {
        cmp.emplace_back(A[i], i);
    }
    for (int i = 0; i < Q; ++i) {
        cmp.emplace_back(V[i], X[i]);
    }
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    const auto index = [&](const int x, const int i) {
        return std::lower_bound(cmp.begin(), cmp.end(), std::make_pair(x, i)) - cmp.begin();  
    };
    const int Size = cmp.size();
    Segtree seg(Size);
    Fenwick fen(Size);
    for (int i = 0; i < N; ++i) {
        fen.add(index(A[i], i), 1);
    }
    for (int i = 0; i < N; ++i) {
        seg.assign(index(A[i], i), i - fen.get(index(A[i], 0)));
    }
    Vec<int> ret(Q);
    for (int i = 0; i < Q; ++i) {
        seg.operate(index(A[X[i]] + 1, 0), Size, 1);
        fen.add(index(A[X[i]], X[i]), -1);
        seg.assign(index(V[i], X[i]), X[i] - fen.get(index(V[i], 0)));
        fen.add(index(V[i], X[i]), -1);
        ret[i] = seg.fold();
        A[X[i]] = V[i];
    }
    return ret;
}
 
#ifdef __APPLE__
int main() {
    int N, Q;
    std::cin >> N >> Q;
    Vec<int> A(N);
    Vec<int> X(Q), V(Q);
    for (auto &x: A) {
        std::cin >> x;
    }
    for (int i = 0; i < Q; ++i) {
        std::cin >> X[i] >> V[i];
    }
    for (auto x: countScans(A, X, V)) {
        std::cout << x << '\n';
    }
    return 0;
}
#endif

Compilation message (stderr)

bubblesort2.cpp: In member function 'void Segtree::operate(int, int, int)':
bubblesort2.cpp:83:20: warning: unused variable 'lc' [-Wunused-variable]
   83 |         const auto lc = l;
      |                    ^~
bubblesort2.cpp:84:20: warning: unused variable 'rc' [-Wunused-variable]
   84 |         const auto rc = r;
      |                    ^~

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