oj.uz

Submission #886993

# Submission time Handle Problem Language Result Execution time Memory
886993 2023-12-13T12:02:31 Z amirhoseinfar1385 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 348 ms 848 KB 
#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+1);
	ret[0]=maxa;
	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+1]=maxa;
	}
	return ret;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -