Submission #1103010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103010		alexander707070	Holiday (IOI14_holiday)	C++14	0 / 100	36 ms	14024 KiB

holiday

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

#define MAXN 500007
using namespace std;

int n,a[MAXN],start;

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,int val){
		if(l==r){
			tree[v].second+=val;
			tree[v].first+=ret[l]*val;
		}else{
			int tt=(l+r)/2;

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

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

	long long getsum(int v,int l,int r,long long k){
		if(k<0)return 0;

		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 pref[MAXN],suff[MAXN];

void solveopt_right(int dl,int dr,int optl,int optr){
	if(dl>dr)return;

	int mid=(dl+dr)/2,opt=optl;
	suff[mid]=0;

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

		long long curr=seg.getsum(1,1,cnt,mid-(i-start));
		if(curr>suff[mid]){
			suff[mid]=curr;
			opt=i;
		}
	}

	for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);

	solveopt_right(dl,mid-1,optl,opt);

	for(int i=optl;i<opt;i++)seg.update(1,1,cnt,a[i],1);
	solveopt_right(mid+1,dr,opt,optr);

	for(int i=optl;i<opt;i++)seg.update(1,1,cnt,a[i],-1);
}

void solveopt_left(int dl,int dr,int optl,int optr){
	if(dl>dr)return;

	int mid=(dl+dr)/2,opt=optr;
	pref[mid]=0;

	for(int i=optr;i>=optl;i--){
		seg.update(1,1,cnt,a[i],1);

		long long curr=seg.getsum(1,1,cnt,mid-2*(start-1-i));
		if(curr>pref[mid]){
			pref[mid]=curr;
			opt=i;
		}
	}

	for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
	
	solveopt_left(dl,mid-1,opt,optr);

	for(int i=opt+1;i<=optr;i++)seg.update(1,1,cnt,a[i],1);
	solveopt_left(mid+1,dr,optl,opt);

	for(int i=opt+1;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
}

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

	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]];

	seg.init();
	solveopt_right(0,d,start,n);

	seg.init();
	solveopt_left(0,d,1,start-1);

	ans=max(ans,pref[d]);
	if(start==1)return ans;

	for(int i=0;i<=d-2;i++){
		ans=max(ans,pref[i]+suff[d-2-i]);
	}

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

	seg.init();
	solveopt_right(0,d,start,n);

	seg.init();
	solveopt_left(0,d,1,start-1);

	ans=max(ans,pref[d]);
	for(int i=0;i<=d-2;i++){
		ans=max(ans,pref[i]+suff[d-2-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:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i=0;i<w.size();i++){
      |              ~^~~~~~~~~

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