Submission #588625

#	Time	Username	Problem	Language	Result	Execution time	Memory
588625		LastRonin	Holiday (IOI14_holiday)	C++14	100 / 100	366 ms	7748 KiB

holiday

#pragma GCC optimize("O3")
 
#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
mt19937_64 bruh(chrono::steady_clock::now().time_since_epoch().count()); 
 
const int N = 150002;
const int M = 150002;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;
 
ll n, strt, d;
ll a[N];
ll szh[N];
ll L, R;
 
struct seg {
	ll t[4 * N] = {0};
	ll ts[4 * N] = {0};
	void upd(ll p, ll c, ll z, ll v = 1, ll tl = 0, ll tr = n) {
		if(tl == tr) {
			t[v] += c;
			ts[v] += z;
			return;
		}
		ll m = (tl + tr) >> 1ll;
		if(p <= m) {
			upd(p, c, z, v * 2, tl, m);
		}
		else {
			upd(p, c, z, v * 2 + 1, m + 1, tr);
		}
		t[v] = t[v * 2] + t[v * 2 + 1];
		ts[v] = ts[v * 2] + ts[v * 2 + 1];
	}
	ll get(ll k, ll v = 1, ll tl = 0, ll tr = n) {
		if(tl == tr) {
			if(t[v] == 0)return 0;
			ll z = ts[v]/t[v];
			return min(t[v], k) * z;
		}
		ll m = (tl + tr) >> 1ll;
		if(k <= t[v * 2 + 1])return get(k, v * 2 + 1, m + 1, tr);
		return get(k - t[v * 2 + 1], v * 2, tl, m) + ts[v * 2 + 1];
	}
} rt;
 
void add(ll pos) {
	rt.upd(szh[pos], 1, a[pos]);
}
void del(ll pos) {
	rt.upd(szh[pos], -1, -a[pos]);
}
 
void sdvig(ll l, ll r) {
	while(R < r) add(++R);
	while(l < L) add(--L);
	while(l > L) del(L++);
	while(R > r) del(R--);
}
 
ll ans[N];
 
void solve(ll l, ll r, ll optl, ll optr) {
	if(l > r)return;
	ll m = (l + r) >> 1ll;
	ll opt = optl;
	ans[m] = -1e18;
	for(ll j = optl; j <= optr; j++) {
		sdvig(m, j);
		ll ost = d - (min(2 * (j - strt) + (strt - m), (strt - m) * 2 + (j - strt)));
		if(ost < 0)continue;
		if(ans[m] < rt.get(ost))
			ans[m] = rt.get(ost), opt = j;					
	}
	solve(l, m - 1, optl, opt);
	solve(m + 1, r, opt, optr);                           
}
 
long long int findMaxAttraction(int na, int start, int D, int attraction[]) {
	n = na;
	vector<int> szha;
	for(int i = 1; i <= n; i++)
		a[i] = attraction[i - 1], szha.pb(a[i]);
	strt = start + 1, d = D;
	sort(szha.begin(), szha.end());
	szha.erase(unique(szha.begin(), szha.end()), szha.end());
	L = 1, R = 0;
	for(int i = 1; i <= n; i++)
		szh[i] = lower_bound(szha.begin(), szha.end(), a[i]) - szha.begin();
	solve(1, strt, strt, n);
	ll answw = 0;
	for(int i = 1; i <= strt; i++)
		answw = max(answw, ans[i]);
	return answw;
} 

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