#include "bubblesort2.h"
#include<bits/stdc++.h>
#define lsb(x) (x &(-x))
using namespace std;
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q=X.size();
int n = A.size();
std::vector<int> answer(Q);
vector<int> dp(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) if (A[j] > A[i]) dp[i]++;
}
for (int i = 0; i < Q; i++) {
for (int j = X[i] + 1; j < n; j++) if (A[X[i]] > A[j]) dp[j]--;
for (int j = 0; j < X[i]; j++) if (A[j] > A[X[i]]) dp[X[i]]--;
A[X[i]] = V[i];
for (int j = X[i] + 1; j < n; j++) if (A[X[i]] > A[j]) dp[j]++;
for (int j = 0; j < X[i]; j++) if (A[j] > A[X[i]]) dp[X[i]]++;
for (auto &e: dp) answer[i] = max(answer[i], e);
}
// for (int j=0;j<Q;j++) {
// answer[j]=X[j];
// }
return answer;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |