Submission #30532

#	Time	Username	Problem	Language	Result	Execution time	Memory
30532		inqr	Holiday (IOI14_holiday)	C++14	0 / 100	5000 ms	10548 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define ll long long
#define pii pair < int , int >
#define DB printf("debug\n");
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define all(x) x.begin() , x.end()
using namespace std;
int citynum,citystart,timee,att;
struct node{
	int sbtrsum,sbtrnc,act;
	node(){
		sbtrsum=0,sbtrnc=0,act=0;
	}
}nd;
node st[400005];
int citynotostp[400005];
int cityatt[100005];
int lastl=1,lastr=0;
void update(int cityno,node n,int ul,int ur,int l,int r,int stp){
	if(l>r||ur<l||r<ul)return;
	//printf("ul=%d ur=%d l=%d r=%d\n",ul,ur,l,r);
	if(ul<=l&&r<=ur){
		citynotostp[cityno]=l;
		st[stp]=n;
		return;
	}
	int m=(l+r)/2;
	update(cityno,n,ul,ur,l,m,stp*2+1);update(cityno,n,ul,ur,m+1,r,stp*2+2);
	st[stp].sbtrnc=st[stp].sbtrsum=st[stp].act=0;
	if(st[stp*2+1].act==1){
		//printf("za1\n");
		st[stp].act=1;
		st[stp].sbtrsum+=st[stp*2+1].sbtrsum;
		st[stp].sbtrnc+=st[stp*2+1].sbtrnc;
	}
	if(st[stp*2+2].act==1){
		//printf("za2\n");
		st[stp].act=1;
		st[stp].sbtrsum+=st[stp*2+2].sbtrsum;
		st[stp].sbtrnc+=st[stp*2+2].sbtrnc;
	}
	//printf("u2:l=%d r=%d sbtrsum=%d sbtrnc=%d act=%d\n",l,r,st[stp].sbtrsum,st[stp].sbtrnc,st[stp].act);
}
ll sumofbestn(int n,int l,int r,int stp){
	if(l>r || n<1 || st[stp].act==0)return 0;
	if(st[stp].sbtrnc==n)return st[stp].sbtrsum;
	int m=(l+r)/2;
	ll ret=0;
	ret+=sumofbestn(st[stp*2+1].sbtrnc,l,m,stp*2+1);
	n-=st[stp].sbtrnc;
	ret+=sumofbestn(n,m+1,r,stp*2+2);
	return ret;
}
void autoupd(int nl,int nr){
	node nodee;
	nodee.act=1;
	nodee.sbtrnc=1;
	while(lastr<nr){
		lastr++;
		nodee.sbtrsum=cityatt[lastr];
		update(lastr,nodee,citynotostp[lastr],citynotostp[lastr],0,citynum-1,0);
	}
	while(nl<lastl){
		lastl--;
		nodee.sbtrsum=cityatt[lastl];
		update(lastl,nodee,citynotostp[lastl],citynotostp[lastl],0,citynum-1,0);
	}
	nodee.act=0;
	while(lastr>nr){
		nodee.sbtrsum=cityatt[lastr];
		update(lastr,nodee,citynotostp[lastr],citynotostp[lastr],0,citynum-1,0);
		lastr--;
	}
	while(lastl<nl){
		nodee.sbtrsum=cityatt[lastl];
		update(lastl,nodee,citynotostp[lastl],citynotostp[lastl],0,citynum-1,0);
		lastl++;
	}
}
ll solve(){
	ll ans=0;
	for(int i=0;i<=timee;i++){
		int cityleft=citystart-i;
		if(cityleft<0)continue;
		for(int j=0;min(j,i)*2+max(i,j)<=timee;j++){
			int cityright=citystart+j;
			if(cityright>=citynum)continue;
			//printf("    cityright=%d\n",cityright);
			autoupd(cityleft,cityright);
			int visitable=timee-min(j,i)*2-max(i,j);
			//printf("	visitable=%d\n",visitable);
			ans=max(ans,sumofbestn(visitable,0,citynum-1,0));
			//printf("    ans=%lld\n",ans);
		}
	}
	return ans;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	citynum=n,citystart=start,timee=d;
	vector < pii > attind;
	for(int i=0;i<n;i++){
		attind.pb(mp(attraction[i],i));
		cityatt[i]=attraction[i];
	}
	sort(all(attind));reverse(all(attind));
	for(int i=0;i<n;i++){
		node nodeee;
		nodeee.sbtrnc=1;
		nodeee.sbtrsum=attind[i].st;
		nodeee.act=0;
		//printf("%d %d\n",attind[i].st,attind[i].nd);
		update(attind[i].nd,nodeee,i,i,0,n-1,0);
	}
    return solve();
}

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: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53