Submission #515698

#	Time	Username	Problem	Language	Result	Execution time	Memory
515698		mosiashvililuka	Holiday (IOI14_holiday)	C++14	0 / 100	59 ms	65540 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],D,pas,jm,n,g[100009],LF[300009][3],RG[300009][3],RR,za,T[100009],l,r,z,k;
map <long long, long long> M;
map <long long, long long>::iterator IT;
vector <long long> seg[300009],B[300009],pr[300009];
void upd(long long q, long long w, long long rr){
	if(q>w) return;
	long long mid=(q+w)/2;
	B[rr].resize(seg[rr].size());pr[rr].resize(seg[rr].size());
	for(long long h=1; h<seg[rr].size(); h++) pr[rr][h]=pr[rr][h-1]+T[f[seg[rr][h]]];
	if(q==w) return;
	seg[rr*2].push_back(0);seg[rr*2+1].push_back(0);
	for(long long h=1; h<seg[rr].size(); h++){
		if(f[seg[rr][h]]<=mid){
			seg[rr*2].push_back(seg[rr][h]);
			B[rr][h]=B[rr][h-1]+1;
		}else{
			seg[rr*2+1].push_back(seg[rr][h]);
			B[rr][h]=B[rr][h-1];
		}
	}
	upd(q,mid,rr*2);
	upd(mid+1,w,rr*2+1);
}
void wv(){
	za=1;
	while(za<a) za*=2;
	for(i=0; i<=za*2; i++){
		seg[i].clear();B[i].clear();pr[i].clear();
	}
	seg[1].push_back(0);
	for(i=1; i<=a; i++){
		seg[1].push_back(i);
	}
	upd(1,a,1);
}
void read(long long q, long long w, long long rr, long long L, long long R){
	if(L>R||q>w||k<=0) return;
	if(R==0||L==seg[rr].size()) return;
	//cout<<q<<" "<<w<<" "<<rr<<" "<<L<<" "<<R<<"    "<<seg[rr].size()<<" "<<k<<"\n";
	if(R-L+1<=k){
		k-=R-L+1;
		z+=pr[rr][R]-pr[rr][L-1];
		return;
	}
	read((q+w)/2+1,w,rr*2+1,((L-1)-B[rr][L-1])+1,R-B[rr][R]);
	read(q,(q+w)/2,rr*2,B[rr][L-1]+1,B[rr][R]);
}
void rec(long long q, long long w, long long qq, long long ww){
	if(q>w) return;
	//cout<<q<<" "<<w<<" "<<qq<<" "<<ww<<"\n";
	long long mid=(q+w)/2,we=0;
	long long qw=0;
	for(long long h=qq; h<=ww; h++){
		k=mid-(h-1)*RR;z=0;
		if(k<=0) break;
		read(1,a,1,1,h);
		//cout<<h<<"\n";
		if(qw<z){
			qw=z;we=h;
		}
	}
	LF[mid][RR]=qw;
	rec(q,mid-1,qq,we);
	rec(mid+1,w,we,ww);
}
long long int findMaxAttraction(int Nn, int start, int Dd, int attraction[]) {
	n=Nn;start++;D=Dd;a=n;
	for(i=1; i<=n; i++){
		g[i]=attraction[i-1];f[i]=g[i];
	}
	for(i=1; i<=n; i++) M[g[i]]=1;
	zx=0;
	for(IT=M.begin(); IT!=M.end(); IT++){
		zx++;M[(*IT).first]=zx;T[zx]=(*IT).first;
	}
	for(i=1; i<=n; i++) g[i]=M[g[i]];
	/*
	for(i=1; i<=a; i++){
		if(i-1>D) break;
		s.push(-f[i]);jm+=f[i];
		//cout<<"+ "<<f[i]<<"\n";
		while(s.size()>max(0LL,D-(i-1))){
			jm-=-s.top();
			//cout<<"- "<<-s.top()<<"\n";
			s.pop();
		}
		pas=max(pas,jm);
	}*/
	/*for(i=1; i<=n; i++){
		cout<<g[i]<<" ";
	}
	cout<<"\n";
	for(i=1; i<=n; i++){
		cout<<T[g[i]]<<" ";
	}
	cout<<"\n";*/
	for(i=start; i<=n; i++){
		f[i-start+1]=g[i];
	}
	a=n-start+1;RR=1;
	wv();
	rec(1,D,1,a);
	//return 0;
	RR=2;
	rec(1,D,1,a);
	for(i=1; i<=D; i++){
		RG[i][1]=LF[i][1];RG[i][2]=LF[i][2];
		LF[i][1]=LF[i][2]=0;
	}
	if(start!=1){
	for(i=start-1; i>=1; i--){
		f[start-1-i+1]=g[i];
	}
	a=start-1;RR=1;
	wv();
	rec(1,D,1,a);
	RR=2;
	rec(1,D,1,a);
	}
	//
	//cout<<RG[D][1];
	return RG[D][1];
}

Compilation message (stderr)

holiday.cpp: In function 'void upd(long long int, long long int, long long int)':
holiday.cpp:12:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(long long h=1; h<seg[rr].size(); h++) pr[rr][h]=pr[rr][h-1]+T[f[seg[rr][h]]];
      |                     ~^~~~~~~~~~~~~~~
holiday.cpp:15:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(long long h=1; h<seg[rr].size(); h++){
      |                     ~^~~~~~~~~~~~~~~
holiday.cpp: In function 'void read(long long int, long long int, long long int, long long int, long long int)':
holiday.cpp:41:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  if(R==0||L==seg[rr].size()) return;
      |           ~^~~~~~~~~~~~~~~~

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