oj.uz

Submission #6872

# Submission time Handle Problem Language Result Execution time Memory
6872 2014-07-08T14:58:46 Z Qwaz 즐거운 채소 기르기 (JOI14_growing) C++
45 / 100
 156 ms 9032 KB 
#include <cstdio>
#include <algorithm>
#include <queue>

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

int n, data[MAX];
priority_queue < pii > fromL, fromR;

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

	int i;
	for(i = 1; i<=n; i++){
		scanf("%d", &data[i]);
		fromL.push(pii(-data[i], -i));
		fromR.push(pii(-data[i], i));
	}
}

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;
bool used[MAX];

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

	for(i = 0; i<n; i++){
		int nowL = 0, nowR = 0;
		do {
			if(used[nowL]) fromL.pop();
			nowL = -fromL.top().second;
		} while(used[nowL]);

		do {
			if(used[nowR]) fromR.pop();
			nowR = fromR.top().second;
		} while(used[nowR]);

		int tL = min(get(left, nowL), get(right, n+1-nowL))-1;
		int tR = min(get(left, nowR), get(right, n+1-nowR))-1;

		int target;
		if(tL < tR){
			target = nowL;
			res += tL;
		} else {
			target = nowR;
			res += tR;
		}

		used[target] = 1;
		update(left, target, -1);
		update(right, n+1-target, -1);
	}

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

int main(){
	input();

	solve();

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3776 KB Output is correct
2 Correct 0 ms 3776 KB Output is correct
3 Correct 0 ms 3776 KB Output is correct
4 Correct 0 ms 3776 KB Output is correct
5 Correct 0 ms 3924 KB Output is correct
6 Correct 0 ms 3924 KB Output is correct
7 Correct 0 ms 3924 KB Output is correct
8 Correct 0 ms 3924 KB Output is correct
9 Correct 0 ms 3924 KB Output is correct
10 Correct 0 ms 3924 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5192 KB Output is correct
2 Correct 76 ms 6472 KB Output is correct
3 Correct 112 ms 9032 KB Output is correct
4 Correct 156 ms 9032 KB Output is correct
5 Correct 132 ms 9032 KB Output is correct
6 Correct 64 ms 6472 KB Output is correct
7 Runtime error 36 ms 9032 KB Program hung waiting for input
8 Halted 0 ms 0 KB -