Submission #696784

#	Time	Username	Problem	Language	Result	Execution time	Memory
696784		vjudge1	Holiday (IOI14_holiday)	C++17	0 / 100	89 ms	24508 KiB

holiday

#include<bits/stdc++.h>
#include "holiday.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)
{
    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--)
	    {
	        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);
}
ll findMaxAttraction(int nn,int ss,int dd,int aa[])
{
    n=nn,st=ss,d=dd;st++;
    for(int i=1;i<=n;i++)
        a[i]=aa[i-1],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);
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:60:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   60 |     for(int i=1;i<=n;i++)
      |     ^~~
holiday.cpp:62:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   62 |  sort(h.begin(),h.end());
      |  ^~~~
holiday.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
   74 | }
      | ^

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