oj.uz

Submission #17256

# Submission time Handle Problem Language Result Execution time Memory
17256 2015-11-10T19:49:43 Z erdemkiraz Holiday (IOI14_holiday) C++
47 / 100
 847 ms 10192 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"

const int N = 1e5 + 5;

ll ans = 0;

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

typedef pair < ll, int > pl;

pl t[N << 2];

vector < int > vs;
int id[N];

void add(int x, int l, int r, int x1) {
	if(l == r) {
		t[x].first += vs[x1 - 1];
		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 -= vs[x1 - 1];
		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);
}

void solveStart() {
	L = 1;
	R = 0;
	memset(t, 0, sizeof(t));
	solve(start, n, 1, n);
}

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

int ord[N];

long long int findMaxAttraction(int N, int Start, int D, int Attraction[]) {
	n = N;
	start = Start + 1;
	d = D;
	for(int i = 0; i < n; i++)
		a[i + 1] = Attraction[i];
	for(int i = 1; i <= n; i++) {
		vs.push_back(a[i]);
		ord[i] = i;
	}
	sort(ord + 1, ord + n + 1, cmp);
	for(int i = 1; i <= n; i++)
		id[ord[i]] = i;
	sort(vs.begin(), vs.end());
	solveStart();
	reverse(a + 1, a + n + 1);
	reverse(id + 1, id + 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 9412 KB Output is correct
2 Correct 0 ms 9412 KB Output is correct
3 Correct 0 ms 9412 KB Output is correct
4 Correct 3 ms 9420 KB Output is correct
5 Correct 0 ms 9420 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 10184 KB Output is correct
2 Correct 687 ms 10188 KB Output is correct
3 Correct 683 ms 10188 KB Output is correct
4 Correct 708 ms 10188 KB Output is correct
5 Correct 847 ms 10184 KB Output is correct
6 Correct 189 ms 9548 KB Output is correct
7 Correct 410 ms 9804 KB Output is correct
8 Correct 519 ms 9800 KB Output is correct
9 Correct 133 ms 9552 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 10184 KB Output is correct
2 Correct 672 ms 10192 KB Output is correct
3 Incorrect 563 ms 9800 KB Output isn't correct
4 Halted 0 ms 0 KB -