Submission #329459

#	Time	Username	Problem	Language	Result	Execution time	Memory
329459		tnk2908	Holiday (IOI14_holiday)	C++14	Compilation error	0 ms	0 KiB

holiday

//
//  main.cpp
//  holiday
//
//  Created by Trần Nam Khánh on 11/21/20.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const long long nax=1e5+1;
const long long inf=1e18;
struct node
{
    long long s,ac;
}seg[5*nax];
void update(long long id,long long l,long long r,long long k,long long val,long long stat)
{
    if(k<l||r<k)return;
    if(l==r)
    {
        seg[id].ac=stat;
        seg[id].s=val;
        return;
    }
    long long mid=(l+r)>>1;
    update(id*2,l,mid,k,val,stat);
    update(id*2+1,mid+1,r,k,val,stat);
    seg[id].ac=seg[id*2].ac+seg[id*2+1].ac;
    seg[id].s=seg[id*2].s+seg[id*2+1].s;
}
long long query(long long id,long long l,long long r,long long x)
{
    long long res=0;
    if(x<0)return 0;
    if(seg[id].ac<=x)
    {
        return seg[id].s;
    }
    long long mid=(l+r)>>1;
    res=query(id*2,l,mid,min(x,seg[id*2].ac))+query(id*2+1,mid+1,r,x-seg[id*2].ac);
    return res;
}
long long n,st,d,a[nax],pl[nax],attraction[nax];
long long dp[nax];
long long ab(long long a)
{
    if(a<0)return -a;else return a;
}
void dc1(long long lo,long long hi,long long lovl,long long hivl)
{
    if(lo>hi)return;
    long long mid=(lo+hi)>>1,x=lovl;
    for(long long i=mid;i<=st;i++)
    {
        update(1,1,n,pl[i],a[i],1);
    }
    for(long long i=lovl;i<=hivl;i++)
    {
        long long tmpd=d-ab(st-mid)-ab(mid-i);
        if(tmpd<0)break;
        update(1,1,n,pl[i],a[i],1);
        long long tmp=query(1,1,n,tmpd);
        if(dp[mid]<tmp)
        {
            dp[mid]=tmp;
            x=i;
        }
    }
    for(long long i=mid;i<=st;i++)
    {
        update(1,1,n,pl[i],0,0);
    }
    for(long long i=x;i<=hivl;i++)update(1,1,n,pl[i],0,0);
    dc1(mid+1,hi,x,hivl);
    for(long long i=lovl;i<=x;i++)update(1,1,n,pl[i],0,0);
    dc1(lo,mid-1,lovl,x);
}
void dc2(long long lo,long long hi,long long lovl,long long hivl)
{
    if(lo>hi)return;
    long long mid=(lo+hi)>>1,x=lovl;
    for(long long i=st;i<=mid;i++)
    {
        update(1,1,n,pl[i],a[i],1);
    }
    for(long long i=hivl;i>=lovl;i--)
    {
        long long tmpd=d-ab(st-mid)-ab(mid-i);
        if(tmpd<0)break;
        update(1,1,n,pl[i],a[i],1);
        long long tmp=query(1,1,n,tmpd);
        if(dp[mid]<tmp)
        {
            dp[mid]=tmp;
            x=i;
        }
    }
    for(long long i=st;i<=mid;i++)
    {
        update(1,1,n,pl[i],0,0);
    }
    for(long long i=lovl;i<=x;i++)update(1,1,n,pl[i],0,0);
    dc2(lo,mid-1,lovl,x);
    for(long long i=x;i<=hivl;i++)update(1,1,n,pl[i],0,0);
    dc2(mid+1,hi,x,hivl);
}
long long findMaxAttraction(long long N, long long start, long long days, long long attraction[])
{
    long long ans=0;
    pair<long long,long long>b[nax];
    n=N;st=start;d=days;
    for(long long i=1;i<=n;i++)
    {
        a[i]=attraction[i-1];
        b[i].first=-a[i];
        b[i].second=i;
        dp[i]=-inf;
    }
    sort(b+1,b+n+1);
    for(long long i=1;i<=n;i++)
    {
        pl[b[i].second]=i;
    }
    dc1(1,st,st+1,n);
    dc2(st,n,1,st-1);
    for(long long i=1;i<=n;i++)ans=max(ans,dp[i]);
    return ans;
}

Compilation message (stderr)

/tmp/ccRwSnTf.o: In function `main':
grader.cpp:(.text.startup+0x8c): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status