Submission #6867

#	Time	Username	Problem	Language	Result	Execution time	Memory
6867		Qwaz	즐거운 채소 기르기 (JOI14_growing)	C++98	0 / 100	20 ms	4992 KiB

growing

#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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55