oj.uz

Submission #285795

# Submission time Handle Problem Language Result Execution time Memory
285795 2020-08-29T15:26:53 Z amoo_safar Holiday (IOI14_holiday) C++17
100 / 100
 578 ms 5624 KB 
#include "holiday.h"

#include <bits/stdc++.h>
#define int ll

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;
const int Log = 20;
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(0ll, d - (st - mid));

	int Ln = L, Rn = l;

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

	ll val, mx = -Inf, opt = l;
	for(int i = Rn; i <= r; i++){
		if(i < mid){
			Ln ++; Rn ++;
			continue;
		} else {
			if(i > mid){
				rm2 = max(0ll, rem - max(0ll, (i - mid - 1)) );
				val = Get(rm2);	
				if(val > mx){
					mx = val;
					opt = i;
				}
			}
		}
		if(i != r){
			Add(Rn, 1);
			Rn ++;
		}
	}
	//Rn = r;
	assert(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(int32_t _n, int32_t _st, int32_t _d, int32_t _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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 4728 KB Output is correct
2 Correct 135 ms 4728 KB Output is correct
3 Correct 206 ms 4728 KB Output is correct
4 Correct 221 ms 4728 KB Output is correct
5 Correct 296 ms 4472 KB Output is correct
6 Correct 63 ms 1536 KB Output is correct
7 Correct 141 ms 2560 KB Output is correct
8 Correct 183 ms 3072 KB Output is correct
9 Correct 47 ms 1280 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 11 ms 512 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 4728 KB Output is correct
2 Correct 207 ms 4728 KB Output is correct
3 Correct 188 ms 2296 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 578 ms 5624 KB Output is correct
9 Correct 559 ms 5496 KB Output is correct