oj.uz

Submission #120785

# Submission time Handle Problem Language Result Execution time Memory
120785 2019-06-25T13:29:56 Z youngyojun Holiday (IOI14_holiday) C++11
100 / 100
 306 ms 45448 KB 
#include "holiday.h"
#include <bits/stdc++.h>
#define upmax(a,b) (a)=max((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 100055;

struct NOD {
	NOD() : sum(0), cnt(0), l(0), r(0) {}

	ll sum;
	int cnt, l, r;
} arr[MAXN*18]; int arrn;
int newNOD() { return ++arrn; }
int pst[MAXN];

int A[MAXN], AO[MAXN], ARO[MAXN];

ll Ans;
int N, X, L;

void makeTree(int bf, int nw, int s, int e, int x, int r) {
	arr[nw].cnt = arr[bf].cnt + 1;
	arr[nw].sum = arr[bf].sum + r;
	if(s == e) return;
	int m = (s+e) >> 1;
	if(x <= m) {
		arr[nw].r = arr[bf].r;
		arr[nw].l = newNOD();
		makeTree(arr[bf].l, arr[nw].l, s, m, x, r);
	} else {
		arr[nw].l = arr[bf].l;
		arr[nw].r = newNOD();
		makeTree(arr[bf].r, arr[nw].r, m+1, e, x, r);
	}
}

ll _get(int bf, int nw, int x) {
	if(!x) return 0;
	if(arr[nw].cnt - arr[bf].cnt == x) return arr[nw].sum - arr[bf].sum;
	int lc = arr[arr[nw].l].cnt - arr[arr[bf].l].cnt;
	if(x <= lc) return _get(arr[bf].l, arr[nw].l, x);
	return (arr[arr[nw].l].sum - arr[arr[bf].l].sum) + _get(arr[bf].r, arr[nw].r, x-lc);
}

ll get(int s, int e, int x) {
	return _get(pst[s-1], pst[e], x);
}

void f(int s, int e, int p, int q) {
	if(s > e || p > q) return;
	int m = (s+e) >> 1;
	ll hc = -INFLL; int hi = -1;
	for(int x = p, xe = min({N, (L+X+m)/2, q}); x <= xe; x++) {
		ll t = get(m, x, min(x-m+1, L-(x+x-m-X)));
		if(t <= hc) continue;
		hc = t;
		hi = x;
	}
	upmax(Ans, hc);
	f(s, m-1, p, hi);
	f(m+1, e, hi, q);
}


ll getAns() {
	iota(AO, AO+N+1, 0);
	sort(AO+1, AO+N+1, [&](int a, int b) {
		return A[a] > A[b];
	});
	for(int i = 1; i <= N; i++) ARO[AO[i]] = i;

	for(int i = 1; i <= N; i++) {
		pst[i] = newNOD();
		makeTree(pst[i-1], pst[i], 1, N, ARO[i], A[i]);
	}

	f(max(1, X-L), X, X, N);

	arrn = 0;

	X = N+1-X;
	reverse(A+1, A+N+1);
	iota(AO, AO+N+1, 0);
	sort(AO+1, AO+N+1, [&](int a, int b) {
		return A[a] > A[b];
	});
	for(int i = 1; i <= N; i++) ARO[AO[i]] = i;
	for(int i = 1; i <= N; i++) {
		pst[i] = newNOD();
		makeTree(pst[i-1], pst[i], 1, N, ARO[i], A[i]);
	}
	f(max(1, X-L), X, X, N);

	return Ans;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	::N = n;
	::X = start + 1;
	::L = d;
	for(int i = 0; i < n; i++)
		::A[i+1] = attraction[i];
    return getAns();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42616 KB Output is correct
2 Correct 34 ms 42616 KB Output is correct
3 Correct 37 ms 42616 KB Output is correct
4 Correct 35 ms 42620 KB Output is correct
5 Correct 70 ms 42616 KB Output is correct
6 Correct 34 ms 42616 KB Output is correct
7 Correct 35 ms 42620 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 44792 KB Output is correct
2 Correct 89 ms 44808 KB Output is correct
3 Correct 92 ms 44816 KB Output is correct
4 Correct 96 ms 44764 KB Output is correct
5 Correct 142 ms 44664 KB Output is correct
6 Correct 50 ms 43216 KB Output is correct
7 Correct 81 ms 43944 KB Output is correct
8 Correct 98 ms 44024 KB Output is correct
9 Correct 49 ms 43128 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42744 KB Output is correct
2 Correct 38 ms 42764 KB Output is correct
3 Correct 37 ms 42744 KB Output is correct
4 Correct 37 ms 42744 KB Output is correct
5 Correct 38 ms 42716 KB Output is correct
6 Correct 34 ms 42720 KB Output is correct
7 Correct 33 ms 42488 KB Output is correct
8 Correct 34 ms 42616 KB Output is correct
9 Correct 34 ms 42624 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 45432 KB Output is correct
2 Correct 92 ms 45428 KB Output is correct
3 Correct 98 ms 43896 KB Output is correct
4 Correct 35 ms 42744 KB Output is correct
5 Correct 34 ms 42624 KB Output is correct
6 Correct 34 ms 42616 KB Output is correct
7 Correct 34 ms 42616 KB Output is correct
8 Correct 305 ms 45448 KB Output is correct
9 Correct 306 ms 45436 KB Output is correct