Submission #70880

#	Time	Username	Problem	Language	Result	Execution time	Memory
70880		alenam0161	Holiday (IOI14_holiday)	C++17	100 / 100	552 ms	60016 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define Rl Root[rt].l
#define Rr Root[rt].r
#define Ll Root[lt].l
#define Lr Root[lt].r
const int N = 1e5+7;
int n,start,d,a[N],cnt,t,main_Root[N];
struct node{
	int l,r,cnt;
	long long val;
}Root[N*30];
void build(int rt,int l,int r){
	Root[rt].cnt=0;Root[rt].val=0;
	if(l==r)return;
	int m=(l+r)/2;
	Rl=++cnt;
	Rr=++cnt;
	build(Rl,l,m);
	build(Rr,m+1,r);
}
void upd(int lt,int rt,int l,int r,long long pos,long long v2){
	Root[rt].cnt=Root[lt].cnt+1;
	Root[rt].val=Root[lt].val+v2;
//	cout<<"update  "<<rt<<" "<< l<<" "<<r<<" "<<pos<<" "<<v2<<" "<<Root[rt].cnt<<" "<<Root[rt].val<<endl;
	if(l==r)return;
	int m=(l+r)/2;
	if(m>=pos){
		Rl=++cnt;
		Rr=Lr;
		upd(Ll,Rl,l,m,pos,v2);
	}
	else {
		Rl=Ll;
		Rr=++cnt;
		upd(Lr,Rr,m+1,r,pos,v2);
	}
	if(Root[rt].val!=Root[Rl].val+Root[Rr].val){
		assert(0);
	}
}
long long get(int lt,int rt,int l,int r,long long k){
	if(k<=0)return 0;
	int opt=Root[rt].cnt-Root[lt].cnt;
	long long val=Root[rt].val-Root[lt].val;
	//cout<<lt<<" "<<rt<< " "<<l<<" "<<r<<" "<<opt<<" "<<val<<" "<<k<<endl;
	if(l==r){
		if(k<=opt){
			return (Root[rt].val-Root[lt].val)/(Root[rt].cnt-Root[lt].cnt)*k;
			assert(0);
		}
		return val;
	}
	long long optr=Root[Rr].cnt-Root[Lr].cnt;
	long long vr=Root[Rr].val-Root[Lr].val;
	int m=(l+r)/2;
	//cout<<optr<<" "<<vr<<" "<<k<<endl;
	if(optr>k){
		return get(Lr,Rr,m+1,r,k);
	}
	else{
		return 	vr+get(Ll,Rl,l,m,k-optr);
	}
}
long long ans=0;
void fnd_ans(int tl,int tr,int l,int r){
	if(tl>tr||l>r)return;
	int m=(l+r)/2;
	int bst=tr;
	long long cur=-1;
	//cout<<start<<" "<<tl<< " "<<tr<<" "<<l<<" "<<r<<endl;
	for(int i=tl;i<=tr;++i){
	//	cout<<i<<" "<<m<<" "<<d-m+i-min(start-i,m-start)<<endl;
		long long c=get(main_Root[i-1],main_Root[m],1,t,d-m+i-min(start-i,m-start));
	//	cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<endl;
	//	cout<<i<<" "<<m<<" "<<c<<endl;
		if(c>cur){
			cur=c;
			bst=i;
		}
	}
	ans=max(ans,cur);
	fnd_ans(tl,bst,l,m-1);
	fnd_ans(bst,tr,m+1,r);
}
map<int,int> how,wh;

long long int findMaxAttraction(int n, int startt, int d, int attraction[]) {
	::n=n,start=startt,::d=d;
	for(int i=0;i<n;++i)a[i]=attraction[i];
	for(int i=0;i<n;++i)wh[a[i]]++;
	for(auto to:wh){
		how[to.first]=++t;
	}
	main_Root[0]=++cnt;
//	cout<<"hi"<<endl;
	build(main_Root[0],1,t);
	//cout<<"end"<<endl;
	for(int i=1;i<=n;++i){
		main_Root[i]=++cnt;
		upd(main_Root[i-1],main_Root[i],1,t,how[a[i-1]],a[i-1]);
	}
//	cout<<t<<endl;
	start++;
	fnd_ans(1,start,start,n);
    return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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