| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 711504 | Cyanmond | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bubblesort2.h"
#include <bits/stdc++.h>
constexpr int inf = 1 << 30;
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;
std::vector<int> countL(N);
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (A[i] > A[j]) {
++countL[j];
}
}
}
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];
for (int i = x + 1; i < N; ++i) {
if (preVal > A[i]) {
--countL[i];
}
}
A[x] = newVal;
for (int i = x + 1; i < N; ++i) {
if (newVal > A[i]) {
++countL[i];
}
}
countL[x] = 0;
for (int i = 0; i < x; ++i) {
if (A[i] > newVal) {
++countL[x];
}
}
answer[q] = *std::max_element(countL.begin(), countL.end());
}
return answer;
}
#include "bubblesort2.h"
#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]);
}