oj.uz

Submission #242658

# Submission time Handle Problem Language Result Execution time Memory
242658 2020-06-28T17:00:27 Z maximath_1 Holiday (IOI14_holiday) C++11
100 / 100
 878 ms 6904 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=4e18;
ll ans=0ll;
pair<int, int>a[100005];
int n, s, d, ptr, pos[100005];
pair<ll, int>st[100005*4];
void upd(int nd, int cl, int cr, int pos, bool is){
	if(cl == cr){
		if(is) st[nd] = {a[pos].first, 1};
		else st[nd] = {0, 0};
		return;
	}
	int md = (cl+cr)/2;
	if(pos<=md) upd(nd*2, cl, md, pos, is);
	else upd(nd*2+1, md+1, cr, pos, is);
	st[nd] = {st[nd*2].first+st[nd*2+1].first, st[nd*2].second+st[nd*2+1].second};
}
ll k_best(int nd, int cl, int cr, int k){
	if(k <= 0) return 0;
	if(st[nd].second <= k) return st[nd].first;
	int md = (cl+cr)/2;
	if(st[nd*2].second >= k)
		return k_best(nd*2, cl, md, k);
	return st[nd*2].first + k_best(nd*2+1, md+1, cr, k-st[nd*2].second);
}
void solve(int l, int r, int opt_l, int opt_r){
	if(l > r) return;
	int md = (l+r)/2;
	pair<ll, int> res = {-inf, -1};
	if(md < ptr)
		for(int i=md; i<ptr; i++)
			upd(1, 1, n, pos[i], true);
	else
		for(int i=ptr; i<md; i++)
			upd(1, 1, n, pos[i], false);
	ptr = md;
	for(int i=opt_l; i<=opt_r; i++){
		upd(1, 1, n, pos[i], true);
		res = max(res, {k_best(1, 1, n, d+2*md-s-i), -i});
	}
	ans = max(ans, res.first);
	int opt = -res.second;
	for(int i=opt; i<=opt_r; i++)
		upd(1, 1, n, pos[i], false);
	solve(md+1, r, opt, opt_r);
	for(int i=opt_l; i<opt; i++)
		upd(1, 1, n, pos[i], false);
	solve(l, md-1, opt_l, opt);
}
ll findMaxAttraction(int N, int S, int D, int A[]){
	n = N, s = S+1, d = D;
	for(int i=1; i<=n; i++)
		a[i] = {A[i-1], i};
	sort(a+1, a+n+1, greater<pair<int, int> >());
	for(int i=1; i<=n; i++)
		pos[a[i].second] = i;
	ptr = s+1;
	solve(1, s, s, n);
	for(int i=1; i<=n; i++){
		pos[n-a[i].second+1] = i;
		upd(1, 1, n, i, false);
	}
	s = n-s+1;
	ptr = s+1;
	solve(1, s, s, n);
	return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 6016 KB Output is correct
2 Correct 210 ms 6136 KB Output is correct
3 Correct 191 ms 6136 KB Output is correct
4 Correct 192 ms 6136 KB Output is correct
5 Correct 232 ms 5880 KB Output is correct
6 Correct 61 ms 1792 KB Output is correct
7 Correct 123 ms 3200 KB Output is correct
8 Correct 148 ms 3328 KB Output is correct
9 Correct 44 ms 1664 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 6008 KB Output is correct
2 Correct 191 ms 6008 KB Output is correct
3 Correct 313 ms 3612 KB Output is correct
4 Correct 16 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 869 ms 6904 KB Output is correct
9 Correct 878 ms 6904 KB Output is correct