Submission #134230

#	Time	Username	Problem	Language	Result	Execution time	Memory
134230		antimirage	Holiday (IOI14_holiday)	C++14	100 / 100	2829 ms	52192 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int N = 1e5 + 3;
 
long long d1[2][(int)3e5], d2[2][(int)3e5];
 
struct tree{
	int cnt, l, r;
	long long sum;
} 
t[N * 19];
 
int n, a[N], sz, st, root[N], D;
 
vector <int> vec;
 
void update (int ov, int nv, int pos, int val, int tl = 0, int tr = n) {
	if (tl == tr) {
		t[nv].cnt = t[ov].cnt + 1; 
		t[nv].sum = t[ov].sum + val;
	} 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, val, tl, tm );
		} else {
			t[nv].l = t[ov].l;
			t[nv].r = ++sz;
			update( t[ov].r, t[nv].r, pos, val, 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 = n) {
	if (tl == tr) {
		return min((t[nv].sum - t[ov].sum), k * 1ll * vec[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;
	if (dm + (opt - st) <= D) 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;
	if (dm + (st - opt) <= D) 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 ASD, int at[]) { start++; D = ASD;
	n = A;
	st = start;
	
	for (int i = 0; i < n; i++) {
		vec.pb(at[i]);
	}
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for (int i = 0; i < n; i++) {
		a[i + 1] = lower_bound(all(vec), at[i]) - vec.begin();
		root[i + 1] = ++sz;
		update( root[i], root[i + 1], a[i + 1], vec[ a[i + 1] ] );
	}
	
	solve1(start, n, 1, min(D, 2 * (n - start) + 1) );
	solve2(1, start - 1, 1, min(D, 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:71:16: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (dm + (opt - st) <= D) d1[1][dm + (opt - st)] = res;
           ~~~~~^~~~~
holiday.cpp: In function 'void solve2(int, int, int, int)':
holiday.cpp:89:15: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (dm + (st - opt) <= D) d2[1][dm + (st - opt)] = res;
           ~~~~^~~~~~

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