제출 #1156028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156028		Hamed_Ghaffari	Bubble Sort 2 (JOI18_bubblesort2)	C++20	60 / 100	9090 ms	4420 KiB

bubblesort2

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

#define SZ(x) int(x.size())

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int n = SZ(A);
	vector<int> inv(n, 0);
	for(int i=0; i<n; i++)
		for(int j=0; j<i; j++)
			inv[i] += A[i]<A[j];
	int q = SZ(X);
	vector<int> ans(q);
	for(int i=0; i<q; i++) {
		inv[X[i]] = 0;
		for(int j=X[i]+1; j<n; j++) inv[j] -= A[j]<A[X[i]];
		A[X[i]] = V[i];
		for(int j=0; j<X[i]; j++) inv[X[i]] += A[X[i]]<A[j];
		for(int j=X[i]+1; j<n; j++) inv[j] += A[j]<A[X[i]];
		ans[i] = 0;
		for(int j=0; j<n; j++) ans[i] = max(ans[i], inv[j]);
	}
	return ans;
}

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