Submission #857458

#	Time	Username	Problem	Language	Result	Execution time	Memory
857458		Abito	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	9035 ms	8532 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
int n,q;
std::vector<int> countScans(std::vector<int> a,std::vector<int> x,std::vector<int> v){
    n=a.size(),q=x.size();
	int b[n];
	vector<int> ans(q);
	for (int i=0;i<n;i++){
        b[i]=0;
        for (int j=0;j<i;j++) b[i]+=bool(a[j]>a[i]);
	}
	for (int k=0;k<q;k++){
        b[x[k]]=0,ans[k]=0;
        for (int i=x[k]+1;i<n;i++) if (a[i]<a[x[k]]) b[i]--;
        a[x[k]]=v[k];
        for (int i=0;i<x[k];i++) b[x[k]]+=bool(a[i]>a[x[k]]);
        for (int i=x[k]+1;i<n;i++) b[i]+=bool(a[x[k]]>a[i]);
        for (int i=0;i<n;i++) ans[k]=max(ans[k],b[i]);
        //for (int i=0;i<n;i++) cout<<b[i]<<' ';
        //cout<<endl;
	}return ans;
}

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