Submission #285767

#	Time	Username	Problem	Language	Result	Execution time	Memory
285767		amoo_safar	Holiday (IOI14_holiday)	C++17	47 / 100	269 ms	4472 KiB

holiday

#include "holiday.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
const int Log = 19;
const ll Inf = 1e18;

int n, st, d, a[N], I[N], ord[N];

ll sum[N], cnt[N];
ll ans = 0;
void Add(int id, int z){
	//cerr << "!! " << id << ' ' << z << '\n';
	int pos = ord[id];
	for(; pos < N; pos += (pos & (-pos)))
		cnt[pos] += z, sum[pos] += a[id] * z;
}
ll Get(int X){
	//cerr << "## " << X << '\n';
	int res = 0;
	ll sm = 0;
	for(int l = Log - 1; l >= 0; l--){
		if(res + (1 << l) >= N) continue;
		if(cnt[res + (1 << l)] > X) continue;
		res |= (1 << l);
		X -= cnt[res];
		sm += sum[res];
	}
	return sm;
}

void Solve(int L, int R, int l, int r){
	if(L >= R) return ;
	int mid = (L + R) >> 1;


	int rm2, rem = max(0, d - (st - mid));

	int Ln = L, Rn = l;

	for(int i = Ln; i < min(mid, Rn); i++) Add(i, -1);
	Ln = mid; Rn = max(Rn, mid);

	ll val, mx = -Inf, opt = l;
	for(int i = Rn; i <= r; i++){
		if(i < mid) val = 0;
		else {
			rm2 = max(0, rem - (i - mid - 1));
			val = Get(rm2);
		}
		if(val > mx){
			mx = val;
			opt = i;
		}
		if(i != r) Add(i, 1);
	}
	Rn = r;
	ans = max(ans, mx);
	//cerr << "$$ " << mid << ' ' << mx << '\n';
	int Lrq = mid + 1, Rrq = opt;

	while(Lrq < Ln) Add(Ln - 1, 1), Ln --;
	while(Rn < Rrq) Add(Rn, 1), Rn ++;
	while(Ln < Lrq) Add(Ln, -1), Ln ++;
	while(Rrq < Rn) Add(Rn - 1, -1), Rn --;

	Solve(mid + 1, R, opt, r);
	Lrq = L, Rrq = l;


	while(Lrq < Ln) Add(Ln - 1, 1), Ln --;
	while(Rn < Rrq) Add(Rn, 1), Rn ++;
	while(Ln < Lrq) Add(Ln, -1), Ln ++;
	while(Rrq < Rn) Add(Rn - 1, -1), Rn --;
	
	Solve(L, mid, l, opt);
}

ll findMaxAttraction(int _n, int _st, int _d, int _a[]) {
    n = _n; st = _st; d = _d;
    for(int i = 0; i < n; i++) a[i] = _a[i];
    iota(I, I + n, 0);
	sort(I, I + n, [&](int i, int j){ return a[i] > a[j]; });
	for(int i = 0; i < n; i++) ord[I[i]] = i + 1;

	Solve(0, st + 1, 0, n);
	
	//cerr << "###################\n";
	reverse(a, a + n);
	st = n - 1 - st;
	iota(I, I + n, 0);
	sort(I, I + n, [&](int i, int j){ return a[i] > a[j]; });
	for(int i = 0; i < n; i++) ord[I[i]] = i + 1;
	Solve(0, st + 1, 0, n);
	
    return ans;
}

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