Submission #329578

#	Time	Username	Problem	Language	Result	Execution time	Memory
329578		hoanghq2004	Holiday (IOI14_holiday)	C++14	100 / 100	557 ms	49508 KiB

holiday

//#define TIOJ
#ifdef TIOJ
#include "lib1899.h"
#else
#include "holiday.h"
#endif

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int maxn=100000+5;
const int maxnode=2000000;
const int INF=(1LL<<60);
struct Node
{
    int lc,rc,size;
    LL Sum;
    Node() {Sum=size=lc=rc=0;}
};
vector<int> disc;
int root[maxn],pmem;
Node mem[maxnode];
int newnode(Node& last)
{
    Node& now=mem[pmem];
    now.lc=last.lc,now.rc=last.rc;
    now.Sum=last.Sum,now.size=last.size;
    return pmem++;
}
void pull(Node& now)
{
    now.Sum=mem[now.lc].Sum+mem[now.rc].Sum;
    now.size=mem[now.lc].size+mem[now.rc].size;
}
void insert(int last,int& cur,int L,int R,LL num)
{  
    cur=newnode(mem[last]);
    Node& now=mem[cur];
    if(L==R) {now.Sum+=disc[num],now.size++;return;}
    LL M=(L+R)>>1;
    if(num<=M) insert(mem[last].lc,now.lc,L,M,num);
    else insert(mem[last].rc,now.rc,M+1,R,num);
    pull(now);
}
LL query(int lt,int rt,LL L,LL R,LL k)
{
    if(L==R) return (LL)disc[L] * min( k ,(LL) mem[rt].size - mem[lt].size );
    LL M=(L+R)>>1,rsize= mem[mem[rt].rc].size - mem[mem[lt].rc].size,rsum=mem[mem[rt].rc].Sum-mem[mem[lt].rc].Sum;
    if(rsize >=k) return query(mem[lt].rc,mem[rt].rc,M+1,R,k);
    return query(mem[lt].lc,mem[rt].lc,L,M,k-rsize)+rsum;
}
inline void buildSeg(int n,int attraction[])
{
    root[0]=0;pmem=1;
    for(LL i=1;i<=n;i++)
        insert(root[i-1],root[i],0,disc.size()-1,lower_bound(disc.begin(),disc.end(),attraction[i-1])-disc.begin());
}
LL solve(int start,int day,int L,int R,int optL,int optR)
{
    LL M=(L+R)>>1,optM=optL,ret=-INF;
    for(int i=optL;i<=optR;i++)
    {
        LL now=query(root[M],root[i+1],0,disc.size()-1, day - (start-M + i-M) );
        if(now>ret) ret=now,optM=i;
    }
    if(L<=M-1) ret=max(ret,solve(start,day,L,M-1,optL,optM));
    if(M+1<=R) ret=max(ret,solve(start,day,M+1,R,optM,optR));
    return ret;
}
LL findMaxAttraction(int n,int start,int day,int attraction[])
{
    disc.clear();
    for(int i=0;i<n;i++) disc.push_back(attraction[i]);
    sort(disc.begin(),disc.end());
    disc.resize(unique(disc.begin(),disc.end())-disc.begin());

    buildSeg(n,attraction);
    LL ans =solve(start,day,0,start,start,n-1);
    
    start=n-start-1;reverse(attraction,attraction+n); 
    buildSeg(n,attraction);
    ans=max(ans,solve(start,day,0,start,start,n-1));    
    return ans;

}

Compilation message (stderr)

holiday.cpp:13:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   13 | const int INF=(1LL<<60);
      |               ~~~~^~~~~

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