Submission #886998

#	Time	Username	Problem	Language	Result	Execution time	Memory
886998		amirhoseinfar1385	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	9033 ms	5184 KiB

bubblesort2

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int dp[maxn],n,q,maxa;

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	n=A.size(),q=X.size(),maxa=0;
	for(int i=0;i<n;i++){
		int ted=0;
		for(int j=i-1;j>=0;j--){
			ted+=A[j]>A[i]?1:0;
		}	
		dp[i]=ted;
		maxa=maxa>ted?maxa:ted;
	}
	vector<int>ret(q);
	for(int i=0;i<q;i++){
		int ind=X[i],w=V[i];
		for(int j=ind+1;j<n;j++){
			dp[j]+=A[ind]>A[j]?-1:0;
		}
		dp[ind]=0;
		A[ind]=w;
		for(int j=ind-1;j>=0;j--){
			dp[ind]+=A[j]>A[ind]?1:0;
		}
		for(int j=ind+1;j<n;j++){
			dp[j]+=A[ind]>A[j]?1:0;
		}
		maxa=0;
		for(int j=0;j<n;j++){
			maxa=maxa>dp[j]?maxa:dp[j];
		}
		ret[i]=maxa;
	}
	return ret;
}

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