Submission #711501

#TimeUsernameProblemLanguageResultExecution timeMemory
711501CyanmondBubble Sort 2 (JOI18_bubblesort2)C++17
0 / 100
2769 ms1068 KiB
#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 (stderr)

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 =
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...