Submission #1102990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102990		alexander707070	Holiday (IOI14_holiday)	C++14	47 / 100	5050 ms	7416 KiB

holiday

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

#define MAXN 500007
using namespace std;

int n,a[MAXN];

vector<int> w;
unordered_map<int,int> mp;
int ret[MAXN],cnt;

long long ans;

struct ST{
	pair<long long,int> tree[4*MAXN];

	void init(){
		for(int i=1;i<=4*cnt;i++){
			tree[i]={0,0};
		}
	}

	pair<long long,int> combine(pair<long long,int> fr,pair<long long,int> sc){
		return {fr.first+sc.first,fr.second+sc.second};
	}

	void update(int v,int l,int r,int pos){
		if(l==r){
			tree[v].second++;
			tree[v].first+=ret[l];
		}else{
			int tt=(l+r)/2;

			if(pos<=tt)update(2*v,l,tt,pos);
			else update(2*v+1,tt+1,r,pos);

			tree[v]=combine(tree[2*v],tree[2*v+1]);
		}
	}

	long long getsum(int v,int l,int r,long long k){
		if(l==r){
			if(tree[v].second<=k)return tree[v].first;
			return k*ret[l];
		}else{
			int tt=(l+r)/2;
			if(tree[2*v+1].second>=k){
				return getsum(2*v+1,tt+1,r,k);
			}else{
				return getsum(2*v,l,tt,k-tree[2*v+1].second) + tree[2*v+1].first;
			}
		}
	}
}seg;

long long solve(int pos,int days){
	if(days<=0)return 0;

	long long res=0;
	seg.init();

	for(int i=pos;i<=n;i++){
		seg.update(1,1,cnt,a[i]);

		if(days-(i-pos)<=0)break;

		res=max(res,seg.getsum(1,1,cnt,days-(i-pos)));
	}

	return res;
}

long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
//long long int findMaxAttraction(int N, int start, int d, vector<int> attraction) {
	n=N; start++;

	for(int i=1;i<=n;i++){
		a[i]=attraction[i-1];
		w.push_back(a[i]);
	}

	sort(w.begin(),w.end());
	for(int i=0;i<w.size();i++){
		if(i==0 or w[i]!=w[i-1])cnt++;
		mp[w[i]]=cnt; ret[cnt]=w[i];
	}

	for(int i=1;i<=n;i++)a[i]=mp[a[i]];

	for(int i=start;i>=1;i--){
		ans=max(ans,solve(i,d-(start-i)));
	}

	if(start!=1){
		reverse(a+1,a+n+1);
		start=n-start+1;

		for(int i=start;i>=1;i--){
			ans=max(ans,solve(i,d-(start-i)));
		}
	}

    return ans;
}

/*int main(){

	cout<<findMaxAttraction(5,2,7,{10,2,20,30,1})<<"\n";

	return 0;
}*/

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=0;i<w.size();i++){
      |              ~^~~~~~~~~

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