Submission #297281

#	Time	Username	Problem	Language	Result	Execution time	Memory
297281		miss_robot	Holiday (IOI14_holiday)	C++14	30 / 100	5050 ms	43760 KiB

holiday

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

#pragma GCC optimize("O3")
#define ll long long

using namespace std;

const int L = 131072;
vector<int> t[2*L];
vector<ll> p[2*L];

int num(int l, int r, int x){
	int s = 0;
	l += L, r += L;
	while(l <= r){
		if(l&1) s += upper_bound(t[l].begin(), t[l].end(), x, greater<int>())-t[l].begin(), l++;
		if(!(r&1)) s += upper_bound(t[r].begin(), t[r].end(), x, greater<int>())-t[r].begin(), r--;
		l >>= 1, r >>= 1;
	}
	return s;
}

ll qry(int l, int r, int x, ll &mi){
	ll s = 0;
	l += L, r += L;
	while(l <= r){
		if(l&1){
			int idx = upper_bound(t[l].begin(), t[l].end(), x, greater<int>())-t[l].begin()-1;
			if(idx >= 0) s += p[l][idx];
			if(idx+1 < (int)p[l].size()) mi = max(mi, (ll)t[l][idx+1]);
			l++;
		}
		if(!(r&1)){
			int idx = upper_bound(t[r].begin(), t[r].end(), x, greater<int>())-t[r].begin()-1;
			if(idx >= 0) s += p[r][idx];
			if(idx+1 < (int)p[r].size()) mi = max(mi, (ll)t[r][idx+1]);
			r--;
		}
		l >>= 1, r >>= 1;
	}
	return s;
}

ll sum(int l, int r, int k){
	k = min(k, r-l+1);
	int a = 0, b = 1e9, m;
	while(a < b){
		if(a == b-1){
			if(num(l, r, a) <= k) b--;
			else a++;
		}
		else{
			m = (a+b)/2;
			if(num(l, r, m) <= k) b = m;
			else a = m+1;
		}
	}
	ll mi = 0, ret = qry(l, r, a, mi);
	ret += mi*(k-num(l, r, a));
	return ret;
}

ll st2(int n, int d){
	ll res = 0;
	for(int i = 0; i < min(n, d); i++) res = max(res, sum(0, i, d-i));
	return res;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]){
	for(int i = 0; i < n; i++) t[i+L] = {attraction[i]}, p[i+L] = {attraction[i]};
	for(int i = L-1; i; i--){
		merge(begin(t[i<<1]), end(t[i<<1]), begin(t[i<<1|1]), end(t[i<<1|1]), back_inserter(t[i]),
				greater<int>());
		for(int j = 0; j < (int)t[i].size(); j++){
			p[i].push_back(t[i][j]);
			if(j) p[i].back() += p[i][p[i].size()-2];
		}
	}
	if(!start) return st2(n, d);
	ll sol = 0;
	for(int i = 0; i <= start; i++){
		for(int j = start; j <= n; j++){
			sol = max(sol, sum(i, j, d-min(j-start, start-i)*2-max(j-start, start-i)));
		}
	}
	return sol;
}

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