Submission #1028246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028246		nishkarsh	Holiday (IOI14_holiday)	C++14	100 / 100	225 ms	43868 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vt vector
#define pb push_back

const int INF = 2e9;
const ll INFLL = 4e18;
const int mod = 1e9+7;
const int N = 1e5+1;
const int logn = 20;

struct tree_node{
	int cnt,lt,rt;
	ll sum;
};

tree_node segtree[N*logn];
int segtree_node_cnt = 0;

int update(int node, int i, int j, int ind, int val){
	int curr_node = ++segtree_node_cnt;
	segtree[curr_node] = segtree[node];
	segtree[curr_node].cnt++;
	segtree[curr_node].sum += val;
	if(i == j) return curr_node;
	int mid = (i+j)>>1;
	if(ind <= mid) segtree[curr_node].lt = update(segtree[node].lt,i,mid,ind,val);
	else segtree[curr_node].rt = update(segtree[node].rt,mid+1,j,ind,val);
	return curr_node;
}

void query(int nodelt, int nodert, int i, int j, int &count, ll &sum) {
	if(count <= 0 || nodert == 0) return;
	if(segtree[nodert].cnt - segtree[nodelt].cnt <= count){
		count -= segtree[nodert].cnt - segtree[nodelt].cnt;
		sum += segtree[nodert].sum - segtree[nodelt].sum;
		return;
	}
	if(i==j){
		ll temp = segtree[nodert].sum - segtree[nodelt].sum;
		temp /= segtree[nodert].cnt - segtree[nodelt].cnt;
		temp *= count;
		count = 0;
		sum += temp;
	}
	else{
		int mid = (i+j)>>1;
		query(segtree[nodelt].rt, segtree[nodert].rt, mid+1, j, count, sum);
		query(segtree[nodelt].lt, segtree[nodert].lt, i, mid, count, sum);
	}
}

int node_nums[N];

long long int find_range_ans(int l, int r, const int &d, const int &start, const bool &repeat_from_left){
	if(start < l || start > r) return 0;
	ll ans = 0;
	int cnt = r-l;
	if(repeat_from_left) cnt += start-l;
	else cnt += r-start;
	cnt = d-cnt;
	query(node_nums[l-1], node_nums[r], 1, N, cnt, ans);
	return ans;
}

void dnc(int lt_l, int lt_r, int rt_l, int rt_r, const bool repeat_from_left, const int &d, ll &ans, const int &start){
	if(rt_l > rt_r) return;
	int rt_mid = (rt_l + rt_r) / 2;
	int lt_mid = lt_l;
	ll curr_ans = 0;
	for(int i = lt_l; i <= lt_r; i++){
		ll curr = find_range_ans(i, rt_mid, d, start, repeat_from_left);
		if(curr >= curr_ans){
			curr_ans = curr;
			lt_mid = i;
		}
	}
	ans = max(ans,curr_ans);

	dnc(lt_l, lt_mid, rt_l, rt_mid - 1, repeat_from_left, d, ans, start);
	dnc(lt_mid, lt_r, rt_mid + 1, rt_r, repeat_from_left, d, ans, start);	
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]){
	start++;
	int temp[n];
	for(int i = 0; i < n; i++) temp[i+1] = attraction[i];
	sort(temp+1,temp+n+1);
	for(int i = 0; i < n; i++){
		int index = lower_bound(temp + 1, temp + n + 1, attraction[i]) - temp;
		node_nums[i+1] = update(node_nums[i], 1, N, index, attraction[i]);
	}
	ll ans = 0;
	if(start == 1){
		for(int i = 1; i <= n; i++) ans = max(ans,find_range_ans(start,i,d,start,true));
		return ans;
	}
	dnc(1, start, start, n, true, d, ans, start);
	dnc(1, start, start, n, false, d, ans, start);
	return ans;
}

void solve(){
	int n,start,d;
	cin >> n >> start >> d;
	int attraction[n];
	for(int i = 0; i < n; i++) cin >> attraction[i];
	cout << findMaxAttraction(n,start,d,attraction) << "\n";
}

// int main() {

// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
// 	cout.tie(0);

// 	int t = 1;
// 	// cin >> t;

// 	while(t--) {
// 		solve();
// 	}

// }

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