Submission #1155965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155965		Otalp	Bubble Sort 2 (JOI18_bubblesort2)	C++20	60 / 100	9091 ms	5260 KiB

bubblesort2

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

int a[500100];
int dp[500100];


vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int t = X.size();
	int n = A.size();
	for(int i=1; i<=n; i++){
		a[i] = A[i-1];
	}
	for(int i=1; i<=n; i++){
		dp[i] = 0;
		for(int j=1; j<=i; j++){
			dp[i] += (a[i] < a[j]);
		}
	}
	vector<int> res;
	for(int j=0; j<t; j++){
		int pos = X[j] + 1;
		int x = V[j];
		for(int i=pos+1; i<=n; i++){
			dp[i] -= (a[i] < a[pos]);
		}
		a[pos] = x;
		for(int i=pos+1; i<=n; i++){
			dp[i] += (a[i] < a[pos]);
		}
		dp[pos] = 0;
		for(int i=1; i<=pos; i++){
			dp[pos] += (a[i] > a[pos]);
		}
		int mx = 0;
		// for(int i=1; i<=n; i++) cout<<a[i]<<'\n';
		for(int i=1; i<=n; i++) mx = max(mx, dp[i]);
		res.pb(mx);
	}
	return res;
}

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