Submission #1293432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293432		Jawad_Akbar_JJ	Holiday (IOI14_holiday)	C++20	100 / 100	979 ms	34532 KiB

holiday

#include <iostream>
#include <map>

using namespace std;
#define ll long long
const ll N = (1<<17) + 1;
ll cr, cnt[N<<1], Sum[N<<1], SumL[N<<2], SumR[N<<2], rgt[N<<2], lft[N<<2], rev[N], a[N];
map<ll, ll> mp, mp2;

void insert(ll i, ll t, ll cur = 1, ll st = 1, ll en = N){
	if (i >= en or i < st)
		return;
	cnt[cur] += t;
	Sum[cur] += t * rev[i];
	
	if (en - st == 1)
		return;	

	ll lc = cur<<1, rc = lc + 1, mid = (st + en)>>1;

	insert(i, t, lc, st, mid);
	insert(i, t, rc, mid, en);
}

ll get(ll k, ll cur = 1, ll st = 1, ll en = N){
	if (en - st == 1)
		return min(k, cnt[cur]) * rev[st];
	ll lc = cur<<1, rc = lc + 1, mid = (st + en)>>1;

	if (cnt[rc] <= k)
		return Sum[rc] + get(k - cnt[rc], lc, st, mid);
	return get(k, rc, mid, en);
}

void solve1(ll l, ll r, ll st, ll en, ll S){
	if (l > r)
		return;
	ll mid = (l + r) / 2;

	rgt[mid] = st;
	for (ll i=st;i<=en;i++){
		// turn it on
		insert(a[i], 1);
		ll nw = get(max(mid - (i - S), 0LL));
		if (SumR[mid] < nw)
			SumR[mid] = nw, rgt[mid] = i;
	}
	
	for (ll i=rgt[mid];i<=en;i++)
		insert(a[i], -1);
	// turn some off
	solve1(mid + 1, r, rgt[mid], en, S);
	
	for (ll i=st;i<rgt[mid];i++)
		insert(a[i], -1);
	// turn remaining off
	solve1(l, mid - 1, st, rgt[mid], S);
}

void solve2(ll l, ll r, ll st, ll en, ll S){
	if (l > r)
		return;
	ll mid = (l + r) / 2;

	lft[mid] = en;
	for (ll i=en;i>=st;i--){
		// turn it on
		insert(a[i], 1);
		ll nw = get(max(mid - (S - i), 0LL));
		if (SumL[mid] < nw)
			SumL[mid] = nw, lft[mid] = i;
	}
	for (ll i=st;i<=lft[mid];i++)
		insert(a[i], -1);
	// turn some off
	solve2(mid + 1, r, st, lft[mid], S);

	for (ll i=lft[mid]+1;i<=en;i++)
		insert(a[i], -1);
	// turn remaining off
	solve2(l, mid - 1, lft[mid], en, S);
}
bool flg;
long long findMaxAttraction(int n, int s, int d, int at[]){
	// cout<<n<<" "<<s<<" "<<d<<endl;
	s += !flg, cr = 0;
	for (ll i=0;i<(N << 2);i++)
		lft[i] = rgt[i] = SumL[i] = SumR[i] = 0;

	for (ll i=1;i<=n;i++)
		a[i] = at[i-1], mp[a[i]];
	if (mp2.size() == 0){
		for (auto [i, j] : mp)
			mp2[i] = ++cr, rev[cr] = i;
	}
	for (ll i=1;i<=n;i++)
		a[i] = mp2[a[i]];

	solve1(0, d + 10, s, n, s);
	if (s > 1)
		solve2(0, d + 10, 1, s - 1, s - 1);

	ll Max = 0;
	for (ll i=0;i<=d;i++){
		ll k = max(0LL, d - (rgt[i] - s) - i - 1);
		Max = max(Max, SumR[i] + SumL[k]);
	}
	for (ll i=0;n - i - 1 > i;i++)
		swap(at[i], at[n - i - 1]);
	if (!flg)
		flg = 1, Max = max(Max, findMaxAttraction(n, n - s + 1, d, at));
	return Max;
}

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