Submission #232118

#	Time	Username	Problem	Language	Result	Execution time	Memory
232118		spdskatr	Holiday (IOI14_holiday)	C++14	0 / 100	20 ms	2048 KiB

holiday

#include"holiday.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cassert>
#include <queue>
#define SZ (1 << 17)
using namespace std;
typedef long long ll;

int val[100005], N, D, pos;
ll ans = 0;
struct ST { ll tot; int cnt; };

struct Segtree {
	ST st[1<<18];
	ST stc(ST a, ST b) {
		return { a.tot + b.tot, a.cnt + b.cnt };
	}
	void seg_ins(int x, int op) {
		int i = x + SZ;
		st[i] = { st[i].tot + x*op, st[i].cnt + op };
		for (; i > 1; i >>= 1) st[i>>1] = stc(st[i], st[i^1]);
	}
	// Sum of cnt largest items in segtree
	ll seg_walk(int cnt) {
		ll res = 0;
		int cur = 1;
		if (cnt > st[1].cnt) return st[1].tot;
		while (cur < SZ) {
			if (st[cur<<1|1].cnt > cnt) {
				cur = cur<<1|1;
			} else {
				res += st[cur<<1|1].tot;
				cnt -= st[cur<<1|1].cnt;
				cur = cur<<1;
			}
		}
		return res;
	}
} st1;

void solve1(int lo, int hi, int l, int r) {
	if (lo >= hi) return;
	int mid = (lo + hi) / 2;
	// Segtree already populated with hi to l-1
	for (int x = hi-1; x >= mid; x--) {
		st1.seg_ins(val[x], 1);
	}
	ll ov = -1; int op = -1;
	for (int k = l; k < r; k++) {
		st1.seg_ins(val[k], 1);
		ll res = st1.seg_walk(D - (min(pos - mid, k - pos) + (k - mid)));
		if (res > ov) {
			ov = res;
			op = k;
		}
	}
	//printf("solve(%d, %d, %d, %d): optimal %d (%lld)\n", lo, hi, l, r, op, ov);
	ans = max(ans, ov);
	assert(op != -1);
	for (int k = l; k < r; k++) st1.seg_ins(val[k], -1);
	solve1(lo, mid, l, op+1);
	for (int k = l; k < r; k++) st1.seg_ins(val[k], 1);
	for (int x = hi-1; x >= mid; x--) st1.seg_ins(val[x], -1);
	solve1(mid+1, hi, op, r);
	for (int k = l; k < r; k++) st1.seg_ins(val[k], -1);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	N = n, D = d, pos = start;
	for (int i = 0; i < n; i++) val[i] = attraction[i];
	solve1(0, start, start, n);
    return ans;
}

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