제출 #384442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384442		keko37	Bubble Sort 2 (JOI18_bubblesort2)	C++14	17 / 100	1022 ms	1336 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

typedef vector <int> vi;

const int MAXN = 2005;

int n, q;
int a[MAXN], br[MAXN];

void upd (int pos, int val) {
	for (int i = pos + 1; i < n; i++) {
		if (a[pos] > a[i]) br[i]--;
		if (val > a[i]) br[i]++;
	}
	a[pos] = val;
	br[pos] = 0;
	for (int i = 0; i < pos; i++) {
		if (a[i] > a[pos]) br[pos]++;
	}
}

int solve () {
	int mx = 0;
	for (int i = 0; i < n; i++) {
		mx = max(mx, br[i]);
	}
	return mx;
}

vi countScans (vi A, vi X, vi V) {
	n = A.size(), q = X.size();
	for (int i = 0; i < n; i++) {
		a[i] = A[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (a[j] > a[i]) br[i]++;
		}
	}
	vi sol;
	for (int i = 0; i < q; i++) {
		upd(X[i], V[i]);
		sol.push_back(solve());
	}
	return sol;
}

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