oj.uz

Submission #588625

# Submission time Handle Problem Language Result Execution time Memory
588625 2022-07-03T17:38:18 Z LastRonin Holiday (IOI14_holiday) C++14
100 / 100
 366 ms 7748 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 700 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2788 KB Output is correct
2 Correct 18 ms 3008 KB Output is correct
3 Correct 20 ms 3008 KB Output is correct
4 Correct 19 ms 3020 KB Output is correct
5 Correct 29 ms 2876 KB Output is correct
6 Correct 9 ms 1492 KB Output is correct
7 Correct 16 ms 1992 KB Output is correct
8 Correct 18 ms 2244 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 2 ms 880 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3628 KB Output is correct
2 Correct 38 ms 7748 KB Output is correct
3 Correct 105 ms 4276 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 366 ms 7592 KB Output is correct
9 Correct 330 ms 7692 KB Output is correct