| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 6116 | 2014-06-20T05:09:06 Z | ainta | 즐거운 채소 기르기 (JOI14_growing) | C++ | 0 ms | 0 KB |
#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);