oj.uz

Submission #711501

# Submission time Handle Problem Language Result Execution time Memory
711501 2023-03-17T06:25:13 Z Cyanmond Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 2769 ms 1068 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>

constexpr int inf = 1 << 30;

int countLIS(std::vector<int> vec) {
    std::vector<int> dp(vec.size(), inf);
    dp[0] = -inf;
    for (const auto e : vec) {
        auto itr = std::lower_bound(dp.begin(), dp.end(), e);
        *itr = e;
    }
    return std::lower_bound(dp.begin(), dp.end(), inf) - dp.begin() - 1;
}

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());
        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 1, 2
    const int M =
        std::max(*std::max_element(A.begin(), A.end()), *std::max_element(V.begin(), V.end())) + 1;
    int stepNum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (A[i] > A[j]) {
                ++stepNum;
            }
        }
    }

    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];
        A[x] = newVal;
        std::reverse(A.begin(), A.end());
        answer[q] = countLIS(A) - 1;
        std::reverse(A.begin(), A.end());
    }
    return answer;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:41:19: warning: unused variable 'preVal' [-Wunused-variable]
   41 |         const int preVal = A[x];
      |                   ^~~~~~
bubblesort2.cpp:27:15: warning: unused variable 'M' [-Wunused-variable]
   27 |     const int M =
      |               ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2769 ms 1068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -