Submission #337350

#	Time	Username	Problem	Language	Result	Execution time	Memory
337350		KoD	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9025 ms	1556 KiB

bubblesort2

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

Vec<int> countScans(Vec<int> A, Vec<int> X, Vec<int> V) {
    const int N = A.size();
    const int Q = X.size();
    Vec<int> big(N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (A[j] > A[i]) {
                big[i] += 1;
            }
        }
    }
    Vec<int> ret(Q);
    for (int i = 0; i < Q; ++i) {
        for (int j = X[i] + 1; j < N; ++j) {
            if (A[X[i]] <= A[j] && V[i] > A[j]) {
                big[j] += 1;
            }
            if (A[X[i]] > A[j] && V[i] <= A[j]) {
                big[j] -= 1;
            }
        }
        A[X[i]] = V[i];
        big[X[i]] = 0;
        for (int j = 0; j < X[i]; ++j) {
            if (A[j] > A[X[i]]) {
                big[X[i]] += 1;
            }
        }
        ret[i] = *std::max_element(big.begin(), big.end());
    }
    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

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