제출 #6117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6117		ainta	즐거운 채소 기르기 (JOI14_growing)	C++98	0 / 100	12 ms	5776 KiB

growing

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
int n, w[300010];
using namespace std;
struct A{
	int a, num;
	bool operator <(const A &p)const{
		return a < p.a;
	}
}ord[300010];
int BIT[300010];
int Sum(int x){
	int r = 0;
	while (x){
		r += BIT[x];
		x -= (x&-x);
	}
	return r;
}
void Add(int x){
	while (x <= n){
		BIT[x]++;
		x += (x&-x);
	}
}
long long Res;
int main()
{
	int i, x, S;
	scanf("%d", &n);
	for (i = 1; i <= n; i++){
		scanf("%d", &w[i]);
		ord[i].a = w[i], ord[i].num = i;
	}
	sort(ord + 1, ord + n + 1);
	for (i = 1; i <= n; i++){
		x = ord[i].num;
		S = x - 1 - Sum(x);
		if (S < n - i - S){
			Res += S;
		}
		else Res += n - i - S;
		Add(x);
	}
	printf("%lld\n", Res);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55