oj.uz

Submission #6867

# Submission time Handle Problem Language Result Execution time Memory
6867 2014-07-08T14:41:45 Z Qwaz 즐거운 채소 기르기 (JOI14_growing) C++
0 / 100
 20 ms 4992 KB 
#include <cstdio>
#include <algorithm>

using namespace std;
typedef pair < int, int > pii;
typedef long long ll;
const int MAX = 200020;

int n, data[MAX], lFull;
pii list[MAX];

void input(){
	scanf("%d", &n);

	int i;
	for(i = 1; i<=n; i++){
		scanf("%d", &data[i]);
		list[lFull++] = pii(data[i], i);
	}

	sort(list, list+lFull);
}

int left[MAX], right[MAX];

int get(int BIT[], int target){
	int ret = 0;
	while(target){
		ret += BIT[target];
		target -= target & -target;
	}

	return ret;
}

void update(int BIT[], int target, int val){
	while(target < MAX){
		BIT[target] += val;
		target += target & -target;
	}
}

ll res;

void solve(){
	int i;
	for(i = 1; i<=n; i++){
		update(left, i, 1);
		update(right, n+1-i, 1);
	}

	int front = 0, rear = 0;
	for(i = 0; i<n; i++){
		int index = list[i].second;

		res += min(get(left, index), get(right, n+1-index))-1;

		update(left, index, -1);
		update(right, n+1-index, -1);
	}

	printf("%lld\n", res);
}

int main(){
	input();

	solve();

	return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4992 KB Output is correct
2 Correct 0 ms 4992 KB Output is correct
3 Correct 0 ms 4992 KB Output is correct
4 Correct 0 ms 4992 KB Output is correct
5 Correct 0 ms 4992 KB Output is correct
6 Correct 0 ms 4992 KB Output is correct
7 Correct 0 ms 4992 KB Output is correct
8 Correct 0 ms 4992 KB Output is correct
9 Correct 0 ms 4992 KB Output is correct
10 Incorrect 0 ms 4992 KB Output isn't correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4992 KB Output is correct
2 Incorrect 0 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4992 KB Output is correct
2 Incorrect 0 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -