oj.uz

Submission #15848

# Submission time Handle Problem Language Result Execution time Memory
15848 2015-07-31T08:16:13 Z myungwoo Holiday (IOI14_holiday) C++14
30 / 100
 1229 ms 14092 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005
#define MAXT 300005
typedef long long lld;

static int N, S, T, K;
static int A[MAXN], P[MAXN];
static lld D[MAXT];

struct Z{
	int a, x;
} B[MAXN];

struct NODE{
	int cnt; lld sum;
	NODE *left, *right;
} container[262144], *root;

NODE *new_node()
{
	NODE *ret = &container[K++];
	ret->cnt = ret->sum = 0;
	ret->left = ret->right = 0;
	return ret;
}

void write(NODE *now, int s, int e, int n, int v)
{
	if (n < s || e < n) return;
	if (s == e){
		if (v >= 0){
			now->cnt = 1;
			now->sum = v;
		}else{
			now->cnt = now->sum = 0;
		}
		return;
	}
	if (!now->left) now->left = new_node(), now->right = new_node();
	int m = (s+e)>>1;
	write(now->left, s, m, n, v);
	write(now->right, m+1, e, n, v);
	now->cnt = now->left->cnt + now->right->cnt;
	now->sum = now->left->sum + now->right->sum;
}

lld get_highest(NODE *now, int s, int e, int &left)
{
	if (left <= 0) return 0;
	if (now->cnt <= left){
		left -= now->cnt;
		return now->sum;
	}
	if (s == e) return 0;
	int m = (s+e)>>1;
	lld ret = get_highest(now->left, s, m, left);
	if (left > 0) ret += get_highest(now->right, m+1, e, left);
	return ret;
}

void calc(int l, int r, int s, int e)
{
	if (s > e) return;
	int m = (s+e)>>1, t;
	D[m] = -1;
	for (int i=l;i<=r;i++){
		write(root, 1, N, P[i], A[i]);
		int left = m-(i-S);
		if (left <= 0) break;
		lld sum = get_highest(root, 1, N, left);
		if (D[m] < sum)
			D[m] = sum, t = i;
	}
	if (s == e) return;
	for (int i=l;i<=r;i++) write(root, 1, N, P[i], -1);
	calc(l, t, s, m-1);
	for (int i=l;i<t;i++) write(root, 1, N, P[i], A[i]);
	calc(t, r, m+1, e);
}

lld proc()
{
	for (int i=1;i<=N;i++) B[i].a = A[i], B[i].x = i;
	sort(B+1, B+N+1, [](const Z &a, const Z &b){
		return a.a > b.a;
	});
	for (int i=1;i<=N;i++) P[B[i].x] = i;
	K = 0; root = new_node();
	calc(S, N, 1, T);
	return D[T];
}

lld findMaxAttraction(int n, int start, int d, int arr[])
{
	N = n, S = start+1, T = d;
	for (int i=1;i<=N;i++) A[i] = arr[i-1];
	lld ret = proc();
	if (!start) return ret;
	reverse(A+1, A+N+1); S = N-S+1;
	return max(ret, proc());
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14084 KB Output is correct
2 Correct 0 ms 14084 KB Output is correct
3 Correct 0 ms 14092 KB Output is correct
4 Correct 0 ms 14084 KB Output is correct
5 Correct 0 ms 14084 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 14092 KB Output is correct
2 Correct 733 ms 14088 KB Output is correct
3 Correct 965 ms 14092 KB Output is correct
4 Correct 724 ms 14084 KB Output is correct
5 Correct 1229 ms 14088 KB Output is correct
6 Correct 360 ms 14088 KB Output is correct
7 Correct 643 ms 14084 KB Output is correct
8 Correct 745 ms 14084 KB Output is correct
9 Correct 268 ms 14084 KB Output is correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14088 KB Output is correct
2 Correct 14 ms 14084 KB Output is correct
3 Correct 18 ms 14088 KB Output is correct
4 Correct 14 ms 14088 KB Output is correct
5 Incorrect 12 ms 14088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 14092 KB Output is correct
2 Correct 1090 ms 14084 KB Output is correct
3 Incorrect 262 ms 14088 KB Output isn't correct
4 Halted 0 ms 0 KB -