Submission #696783

#	Time	Username	Problem	Language	Result	Execution time	Memory
696783		vjudge1	Holiday (IOI14_holiday)	C++17	Compilation error	0 ms	0 KiB

holiday

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
int n,m,st,d,cnt,rt[N],a[N];
ll f[5][N*3];
vector<int>h;
struct node{ll sum;int cnt,l,r;}t[32*N];
void insert(int las,int &x,int l,int r,int X)
{
    x=++cnt;t[x]=t[las];
    if(l==r)return t[x].sum+=h[X-1],t[x].cnt++,void();
    int mid=(l+r)>>1;
    if(X<=mid)insert(t[las].l,t[x].l,l,mid,X);
    else insert(t[las].r,t[x].r,mid+1,r,X);
    t[x].sum=t[t[x].l].sum+t[t[x].r].sum;
    t[x].cnt=t[t[x].l].cnt+t[t[x].r].cnt;
}
ll query(int ls,int rs,int l,int r,int res)
{
    if(res<0)return -1e18;
    if(l==r)return 1ll*h[l-1]*min(res,t[rs].cnt-t[ls].cnt);
    int mid=(l+r)>>1;
    if(t[t[rs].r].cnt-t[t[ls].r].cnt>=res)
        return query(t[ls].r,t[rs].r,mid+1,r,res);
    return t[t[rs].r].sum-t[t[ls].r].sum+
    query(t[ls].l,t[rs].l,l,mid,res-t[t[rs].r].cnt+t[t[ls].r].cnt);
}
void solve(int T,int l,int r,int L,int R)
{
//	cout<<T<<' '<<l<<' '<<r<<' '<<L<<' '<<R<<endl;
    if(l>r||L>R)return;
    if(l==r)
    {
        for(int i=L;i<=R;i++)
            if(T<3)f[T][i]=query(rt[min(st,l)-1],rt[max(st,l)],1,m,i-(2-T%2)*abs(st-l));
            else f[T][i]=query(rt[min(st-1,l)-1],rt[max(st-1,l)],1,m,i-(2-T%2)*abs(st-l));
        return;
    }
    int M=(L+R)>>1,pos=-1;f[T][M]=-1e18-1;
    ll now;
    if(T<3) 
	    for(int i=l;i<=r;i++)
	    {
	        now=query(rt[min(st,i)-1],rt[max(st,i)],1,m,M-(2-T%2)*abs(st-i));
	        if(now>=f[T][M])f[T][M]=now,pos=i;
	    }
    else
	    for(int i=r;i>=l;i--)
	    {
//	    	if(T==4&&l==1&&r==30123)printf("[%d,%d],%d\n",min(st-1,i)-1,max(st-1,i),M-(2-T%2)*abs(st-i));
	        now=query(rt[min(st-1,i)-1],rt[max(st-1,i)],1,m,M-(2-T%2)*abs(st-i));
	        if(now>=f[T][M])f[T][M]=now,pos=i;
	    }
    if(T<3)solve(T,l,pos,L,M-1),solve(T,pos,r,M+1,R);
    else solve(T,l,pos,M+1,R),solve(T,pos,r,L,M-1);
}
signed main()
{
//	freopen("3.out","r",stdin);
//	freopen("1.out","w",stdout); 
    scanf("%d%d%d",&n,&st,&d);st++;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),h.push_back(a[i]);
	sort(h.begin(),h.end());
	h.erase(unique(h.begin(),h.end()),h.end());
	m=h.size();
    for(int i=1;i<=n;i++)
		a[i]=lower_bound(h.begin(),h.end(),a[i])-h.begin()+1, 
		insert(rt[i-1],rt[i],1,m,a[i]);
    solve(1,st,n,1,d);solve(2,st,n,1,d);
    solve(3,1,st-1,1,d);solve(4,1,st-1,1,d);
    ll ans=0;
    for(int i=0;i<=d;i++)
        ans=max(ans,max(f[1][i]+f[4][d-i],f[2][i]+f[3][d-i]));
    printf("%lld\n",ans);
//    printf("%d\n",ppcnt);
}

Compilation message (stderr)

holiday.cpp: In function 'int main()':
holiday.cpp:63:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   63 |     for(int i=1;i<=n;i++)
      |     ^~~
holiday.cpp:65:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |  sort(h.begin(),h.end());
      |  ^~~~
holiday.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d%d%d",&n,&st,&d);st++;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d",&a[i]),h.push_back(a[i]);
      |         ~~~~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccM1FkhW.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccTqKwMS.o:holiday.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccM1FkhW.o: in function `main':
grader.cpp:(.text.startup+0xaf): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status