Submission #134190

#	Time	Username	Problem	Language	Result	Execution time	Memory
134190		antimirage	Holiday (IOI14_holiday)	C++14	24 / 100	97 ms	65540 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

long long d1[2][(int)3e6], d2[2][(int)3e6];

struct tree{
	int cnt, l, r;
	long long sum;
} 
t[N * 30];

int n, a[N], sz, st, root[N];

void update (int ov, int nv, int pos, int tl = 0, int tr = 1e9) {
	if (tl == tr) {
		t[nv].cnt = t[ov].cnt + 1; 
		t[nv].sum = t[ov].sum + tl;
	} else {
		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			t[nv].r = t[ov].r;
			t[nv].l = ++sz;
			update( t[ov].l, t[nv].l, pos, tl, tm );
		} else {
			t[nv].l = t[ov].l;
			t[nv].r = ++sz;
			update( t[ov].r, t[nv].r, pos, tm + 1, tr );
		}
		t[nv].cnt = t[ t[nv].l ].cnt + t[ t[nv].r ].cnt;
		t[nv].sum = t[ t[nv].l ].sum + t[ t[nv].r ].sum;
	}
}
long long get (int ov, int nv, int k, int tl = 0, int tr = 1e9) {
	if (tl == tr) {
		return min((t[nv].sum - t[ov].sum), k * 1ll * tl);
	}
	int tm = (tl + tr) >> 1;
	
	if (t[t[nv].r].cnt - t[t[ov].r].cnt >= k) {
		return get(t[ov].r, t[nv].r, k, tm + 1, tr);
	}
	return get(t[ov].l, t[nv].l, k - (t[t[nv].r].cnt - t[t[ov].r].cnt), tl, tm ) + t[t[nv].r].sum - t[t[ov].r].sum;
}

void solve1 (int opl, int opr, int dl, int dr) {
	if (dl > dr) return;
	int dm = (dl + dr) >> 1, opt;
	long long res = 0, val;
	
	for (int i = opl; i <= opr; i++) {
		if ( dm - (i - st) <= 0 ) break;
		val = get(root[st - 1], root[i], dm - (i - st));
		if ( val > res ) {
			res = val;
			opt = i;
		}
	}
	d1[0][dm] = res;
	d1[1][dm + (opt - st)] = res;
	solve1(opl, opt, dl, dm - 1);
	solve1(opt, opr, dm + 1, dr);
}
void solve2 (int opl, int opr, int dl, int dr) {
	if (dl > dr || opl > opr) return;
	int dm = (dl + dr) >> 1, opt;
	long long res = 0, val;
	
	for (int i = opr; i >= opl; i--) {
		if ( dm - (st - i) <= 0 ) break;
		val = get(root[i - 1], root[st - 1], dm - (st - i));
		if ( val > res ) {
			res = val;
			opt = i;
		}
	}
	d2[0][dm] = res;
	d2[1][dm + (st - opt)] = res;
	solve2(opl, opt, dm + 1, dr);
	solve2(opt, opr, dl, dm - 1);
}
long long findMaxAttraction(int A, int start, int D, int at[]) { start++;
	n = A;
	st = start;
	
	for (int i = 0; i < n; i++) {
		a[i + 1] = at[i];
		root[i + 1] = ++sz;
		update( root[i], root[i + 1], a[i + 1] );
	}
	solve1(start, n, 1, 2 * (n - start) + 1);
	solve2(1, start - 1, 1, 2 * (start - 1) + 1);
	
	for (int i = 1; i <= D; i++) {
		d1[0][i] = max(d1[0][i - 1], d1[0][i]);
		d1[1][i] = max(d1[1][i - 1], d1[1][i]);
		d2[0][i] = max(d2[0][i - 1], d2[0][i]);
		d2[1][i] = max(d2[1][i - 1], d2[1][i]);
	}
	
	long long ans = 0;
	for (int i = 0; i <= D; i++) {
		ans = max(ans, d1[1][i] + d2[0][D - i]);
		ans = max(ans, d1[0][i] + d2[1][D - i]);
	}
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve1(int, int, int, int)':
holiday.cpp:63:18: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  d1[1][dm + (opt - st)] = res;
             ~~~~~^~~~~
holiday.cpp: In function 'void solve2(int, int, int, int)':
holiday.cpp:81:17: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  d2[1][dm + (st - opt)] = res;
             ~~~~^~~~~~

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