Submission #6117

# Submission time Handle Problem Language Result Execution time Memory
6117 2014-06-20T05:09:19 Z ainta 즐거운 채소 기르기 (JOI14_growing) C++
0 / 100
12 ms 5776 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);
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 5776 KB Output is correct
2 Correct 0 ms 5776 KB Output is correct
3 Correct 0 ms 5776 KB Output is correct
4 Correct 0 ms 5776 KB Output is correct
5 Correct 0 ms 5776 KB Output is correct
6 Correct 0 ms 5776 KB Output is correct
7 Correct 0 ms 5776 KB Output is correct
8 Correct 0 ms 5776 KB Output is correct
9 Correct 0 ms 5776 KB Output is correct
10 Incorrect 0 ms 5776 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 5776 KB Output is correct
2 Incorrect 0 ms 5776 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 5776 KB Output is correct
2 Incorrect 0 ms 5776 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 5776 KB Output isn't correct
2 Halted 0 ms 0 KB -