oj.uz

Submission #17259

# Submission time Handle Problem Language Result Execution time Memory
17259 2015-11-10T19:57:11 Z erdemkiraz Holiday (IOI14_holiday) C++
47 / 100
 846 ms 10592 KB 
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include"holiday.h"

#define int long long

const int N = 1e5 + 5;

ll ans = 0;

int n, start, d;
int a[N];

typedef pair < ll, int > pl;

pl t[N << 2];
int id[N], ord[N];

void add(int x, int l, int r, int x1) {
	if(l == r) {
		t[x].first += a[ord[x1]];
		t[x].second += 1;
		return;
	}
	int m = l + r >> 1;
	if(x1 <= m)
		add(x + x, l, m, x1);
	else
		add(x + x + 1, m + 1, r, x1);
	t[x] = make_pair(t[x + x].first + t[x + x + 1].first, t[x + x].second + t[x + x + 1].second);
}

void del(int x, int l, int r, int x1) {
	if(l == r) {
		t[x].first -= a[ord[x1]];
		t[x].second -= 1;
		return;
	}
	int m = l + r >> 1;
	if(x1 <= m)
		del(x + x, l, m, x1);
	else
		del(x + x + 1, m + 1, r, x1);
	t[x] = make_pair(t[x + x].first + t[x + x + 1].first, t[x + x].second + t[x + x + 1].second);
}

ll get(int x, int l, int r, int k) {
	if(l == r) {
		return t[x].first * (!!k);
	}
	int m = l + r >> 1;
	if(t[x + x + 1].second >= k)
		return get(x + x + 1, m + 1, r, k);
	return t[x + x + 1].first + get(x + x, l, m, k - t[x + x + 1].second);
}

int L, R;

void fix(int l, int r) {
	while(R < r) add(1, 1, n, id[++R]);
	while(R > r) del(1, 1, n, id[R--]);
	while(L > l) add(1, 1, n, id[--L]);
	while(L < l) del(1, 1, n, id[L++]);
}

void solve(int l, int r, int optL, int optR) {
	//printf("l = %d r = %d optL = %d optR = %d\n", l, r, optL, optR);
	if(l > r)
		return;
	int m = l + r >> 1;
	ll res = 0;
	int opt = -1;
	for(int i = optL; i <= optR; i++) {
		if(i > m)
			break;
		fix(i, m);
		ll ret = get(1, 1, n, d - (m - i) - (m - start));
		//printf("i = %d m = %d ret = %d\n", i, m, ret);
		if(opt == -1 or ret > res) {
			ans = max(ans, ret);
			res = ret;
			opt = i;
		}
	}
	solve(l, m - 1, optL, opt);
	solve(m + 1, r, opt, optR);
}

bool cmp(int x, int y) {
	return a[x] < a[y];
}

void solveStart() {
	for(int i = 1; i <= n; i++)
		ord[i] = i;
	sort(ord + 1, ord + n + 1, cmp);
	for(int i = 1; i <= n; i++)
		id[ord[i]] = i;
	L = 1;
	R = 0;
	memset(t, 0, sizeof(t));
	solve(start, n, 1, n);
}

#undef int
long long int findMaxAttraction(int N, int Start, int D, int Attraction[]) {
#define int long long
	n = N;
	start = Start + 1;
	d = D;
	for(int i = 0; i < n; i++)
		a[i + 1] = Attraction[i];
	solveStart();
	reverse(a + 1, a + n + 1);
	start = n - start + 1;
	solveStart();
	return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 10584 KB Output is correct
2 Correct 685 ms 10592 KB Output is correct
3 Correct 664 ms 10588 KB Output is correct
4 Correct 678 ms 10592 KB Output is correct
5 Correct 846 ms 10588 KB Output is correct
6 Correct 185 ms 10592 KB Output is correct
7 Correct 410 ms 10592 KB Output is correct
8 Correct 532 ms 10588 KB Output is correct
9 Correct 129 ms 10588 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10584 KB Output is correct
2 Correct 13 ms 10584 KB Output is correct
3 Correct 9 ms 10588 KB Output is correct
4 Correct 21 ms 10588 KB Output is correct
5 Correct 19 ms 10588 KB Output is correct
6 Correct 7 ms 10584 KB Output is correct
7 Correct 7 ms 10584 KB Output is correct
8 Correct 7 ms 10588 KB Output is correct
9 Correct 4 ms 10584 KB Output is correct

Subtask #4
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 10588 KB Output is correct
2 Correct 664 ms 10584 KB Output is correct
3 Incorrect 558 ms 10588 KB Output isn't correct
4 Halted 0 ms 0 KB -