Submission #17273

#	Time	Username	Problem	Language	Result	Execution time	Memory
17273		erdemkiraz	Holiday (IOI14_holiday)	C++98	100 / 100	475 ms	7624 KiB

holiday

#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 = 1 << 17;

ll ans = 0;

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

typedef pair < ll, int > pl;

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

void add(int x) {
	t[x + N] = ii(a[ord[x]], 1);
	x += N;
	while(x > 1) {
		x >>= 1;
		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) {
	t[x + N] = ii(0, 0);
	x += N;
	while(x > 1) {
		x >>= 1;
		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 k) {
	int x = 1;
	ll ans = 0;
	while(x < N) {
		if(t[x + x + 1].second >= k)
			x = x + x + 1;
		else {
			k -= t[x + x + 1].second;
			ans += t[x + x + 1].first;
			x = x + x;
		}
	}
	ans += (k > 0) * t[x].first;
	return ans;
}

int L, R;

void fix(int l, int r) {
	while(R < r) add(id[++R]);
	while(L > l) add(id[--L]);
	while(R > r) del(id[R--]);
	while(L < l) del(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(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));
	for(int i = start; i <= n; i++) {
		add(id[i]);
		ans = max(ans, get(d - (i - start)));
	}
	memset(t, 0, sizeof(t));
	solve(start, n, 1, start);
}

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];
	solveStart();
	reverse(a + 1, a + n + 1);
	start = n - start + 1;
	solveStart();
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53