Submission #894004

#	Time	Username	Problem	Language	Result	Execution time	Memory
894004		vovik	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9019 ms	2380 KiB

bubblesort2

#include <bits/stdc++.h>

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);

int get(std::vector<int>&a) {
    std::vector<int> x(a.size());
    iota(x.begin(), x.end(), 0);
    stable_sort(x.begin(), x.end(), [&](const int&i, const int&j) { return a[i] < a[j]; });
    int ans = 0;
    for (int i = 0; i < x.size(); ++i) ans = std::max(ans, x[i] - i);
    return ans;
}

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
    int q = X.size();
    std::vector<int> answer(q);
    for (int j = 0; j < q; j++) A[X[j]] = V[j], answer[j] = get(A);
    return answer;
}


#ifdef __APPLE__
#include <cstdio>
#include <cstdlib>
#include <vector>

int readInt() {
    int i;
    if (scanf("%d", &i) != 1) {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
    }
    return i;
}

int main() {
    int N, Q;
    N = readInt();
    Q = readInt();

    std::vector<int> A(N);
    for (int i = 0; i < N; i++)
        A[i] = readInt();

    std::vector<int> X(Q), V(Q);
    for (int j = 0; j < Q; j++) {
        X[j] = readInt();
        V[j] = readInt();
    }

    std::vector<int> res = countScans(A, X, V);

    for (int j = 0; j < int(res.size()); j++)
        printf("%d\n", res[j]);
}
#endif

Compilation message (stderr)

bubblesort2.cpp: In function 'int get(std::vector<int>&)':
bubblesort2.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < x.size(); ++i) ans = std::max(ans, x[i] - i);
      |                     ~~^~~~~~~~~~

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