Submission #1013132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013132		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9062 ms	2360 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define pb push_back

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    int Q=X.size();
    std::vector<int> answer;
    int n=A.size();
    int dp[A.size()];
    dp[0]=0;
    for(int i=1;i<n;i++){
        dp[i]=0;
        for(int j=i-1;j>=0;j--){
            if(A[j]>A[i])
                dp[i]++;
        }
    }
    for(int i=0;i<Q;i++){
        dp[X[i]]=0;
        for(int j=X[i]-1;j>=0;j--){
            if(A[j]>V[i])
                dp[X[i]]++;
        }
        for(int j=X[i]+1;j<n;j++){
            if(V[i]>A[j] && A[j]>=A[X[i]])
                dp[j]++;
            else{
                if(V[i]<=A[j] && A[X[i]]>A[j])
                    dp[j]--;
            }
        }
        A[X[i]]=V[i];
        answer.pb(*max_element(dp,dp+n));
    }
    return answer;
}

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