Submission #52743

#	Time	Username	Problem	Language	Result	Execution time	Memory
52743		zetapi	Holiday (IOI14_holiday)	C++14	23 / 100	934 ms	11668 KiB

holiday

//#include <holiday.h>
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define ll long long
#define itr ::iterator 
 
typedef pair<ll,ll>  pii;
 
const int MAX=3e5;
 
struct data
{
	ll ind;
	ll sum;
}	seg[MAX];
 
vector<pii> sorted;
 
ll N,D,Start,f[MAX],g[MAX],pos[MAX];
 
void build(int low,int high,int node)
{
	if(low==high)
	{
		if(low<=sorted.size())
		{
			seg[node].ind=1;
			seg[node].sum=sorted[low-1].first;
		}
		else
		{
			seg[node].ind=0;
			seg[node].sum=0;
		}
		return ;
	}
	int mid=(low+high)/2;
	build(low,mid,2*node);
	build(mid+1,high,2*node+1);
	seg[node].ind=seg[2*node].ind+seg[2*node+1].ind;
	seg[node].sum=seg[2*node].sum+seg[2*node+1].sum;
	return ;
}
 
void update(int low,int high,int node,int idx,int delta)
{
	if(low==high)
	{
		seg[node].ind=delta;
		if(delta)
			seg[node].sum=sorted[low-1].first;
		else
			seg[node].sum=0;
		return ;
	}
	int mid=(low+high)/2;
	if(idx>=low and idx<=mid)
		update(low,mid,2*node,idx,delta);
	else
		update(mid+1,high,2*node+1,idx,delta);
	seg[node].ind=seg[2*node].ind+seg[2*node+1].ind;
	seg[node].sum=seg[2*node].sum+seg[2*node+1].sum;
	return ;
} 
 
ll query(int low,int high,int node,int K)
{
	if(low==high)
		return seg[node].sum;
	int mid=(low+high)/2;
	if(seg[2*node].ind>=K)
		return query(low,mid,2*node,K);
	return seg[2*node].sum+query(mid+1,high,2*node+1,K-seg[2*node].ind);
}
 
ll cal(int idx,int qlow,int qhigh)
{
	int rem;
	pii res=mp(0,-qlow);
	for(int A=qhigh;A>=qlow;A--)
	{
		rem=idx-(A-Start);
		if(rem>0)
			res=max(res,mp(query(1,N,1,rem),(ll)-A));
		update(1,N,1,pos[A],0);
	}
	for(int A=qlow;A<=qhigh;A++)
		update(1,N,1,pos[A],1);
	return -res.second;
}
 
ll cal2(int idx,int qlow,int qhigh)
{
	int rem;
	pii res=mp(0,qhigh);
	for(int A=qlow;A<=qhigh;A++)
	{	
		rem=idx-(Start-A);
		if(rem>0)
			res=max(res,mp(query(1,N,1,rem),(ll)A));
		update(1,N,1,pos[A],0);
	}
	for(int A=qlow;A<=qhigh;A++)
		update(1,N,1,pos[A],1);
	return res.second;
}
 
void cal(int low,int high,int qlow,int qhigh)
{
	if(low>high)
		return ;
	int mid=(low+high)/2;
	f[mid]=cal(mid,qlow,qhigh);
	if(low==high)
	{
		for(int A=qlow+1;A<qhigh;A++)
			update(1,N,1,pos[A],0);
		return ;
	}
	cal(mid+1,high,f[mid],qhigh);
	cal(low,mid-1,qlow,f[mid]);
	return ;
}
 
void cal2(int low,int high,int qlow,int qhigh)
{
	if(low>high)
		return ;
	int mid=(low+high)/2;
	g[mid]=cal2(mid,qlow,qhigh);
	if(low==high)
	{
		for(int A=qlow;A<qhigh;A++)
			update(1,N,1,pos[A],0);
		return ;
	}
	cal2(mid+1,high,qlow,g[mid]);
	cal2(low,mid-1,g[mid],qhigh);
	return ;
}
 
long long int findMaxAttraction(int n,int start,int d,int attraction[])
{
	N=n;
	D=d;
	Start=start+1;
	ll cur,res=0;
	for(int A=start;A<N;A++)
		sorted.pb(mp(attraction[A],A+1));
	sort(sorted.begin(),sorted.end());
	reverse(sorted.begin(),sorted.end());
	for(int A=0;A<sorted.size();A++)
		pos[sorted[A].second]=A+1;
	build(1,N,1);
	cal(1,D,Start,min(Start+D,N));
	sorted.clear();
	for(int A=0;A<=start;A++)
		sorted.pb(mp(attraction[A],A+1));
	sort(sorted.begin(),sorted.end());
	reverse(sorted.begin(),sorted.end());
	for(int A=0;A<sorted.size();A++)
		pos[sorted[A].second]=A+1;
	build(1,N,1);
	cal2(1,D,max((ll)1,Start-D),Start);
	int ok,ptr=Start,ptr1=1,Starting,last,remain;
	f[0]=Start;
	g[0]=Start;
	sorted.clear();
	for(int A=0;A<N;A++)
		sorted.pb(mp(attraction[A],A+1));
	sort(sorted.begin(),sorted.end());
	reverse(sorted.begin(),sorted.end());
	for(int A=0;A<sorted.size();A++)
		pos[sorted[A].second]=A+1;
	build(1,N,1);
	for(int A=Start;A<=N;A++)
		update(1,N,1,pos[A],0);
	for(int A=0;A<=D;A++)
	{
		ok=A%2;
		cur=A/2;
		last=f[cur];
		remain=D-A;
		if(remain<0)
			break;
		Starting=g[remain];
		remain-=Start-Starting;
		remain+=ok;
		if(remain<0)
			break;
		while(ptr<=last)
			update(1,N,1,pos[ptr++],1);
		while(ptr1<Starting)
			update(1,N,1,pos[ptr1++],0);
		res=max(res,query(1,N,1,remain));
	}
	build(1,N,1);
	for(int A=1;A<=Start;A++)
		update(1,N,1,pos[A],0);
	ptr=Start;
	ptr1=N;
	for(int A=0;A<=D;A++)
	{
		ok=A%2;
		cur=A/2;
		Starting=g[cur];
		remain=D-A;
		if(remain<0)
		   break;
		last=f[remain];
		remain-=last-Start;
		remain+=ok;
		if(remain<0)
			break;
		while(ptr>=Starting)
			update(1,N,1,pos[ptr--],1);
		while(ptr1>last)
			update(1,N,1,pos[ptr1--],0);
		res=max(res,query(1,N,1,remain));	
    // break;
	}
	return res;
}

Compilation message (stderr)

holiday.cpp: In function 'void build(int, int, int)':
holiday.cpp:28:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(low<=sorted.size())
      ~~~^~~~~~~~~~~~~~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:155:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<sorted.size();A++)
              ~^~~~~~~~~~~~~~
holiday.cpp:164:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<sorted.size();A++)
              ~^~~~~~~~~~~~~~
holiday.cpp:176:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<sorted.size();A++)
              ~^~~~~~~~~~~~~~
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: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53