Submission #329483

#	Time	Username	Problem	Language	Result	Execution time	Memory
329483		tnk2908	Holiday (IOI14_holiday)	C++14	100 / 100	973 ms	8172 KiB

holiday

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

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int nax=1e5+1;
const int inf=1e9;
struct node
{
    long long s;
    int ac;
}seg[4*nax];
void build(int id,int l,int r)
{
    seg[id].s=0;
    seg[id].ac=0;
    if(l==r)
    {

        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int k,int val,int stat)
{
    if(k<l||r<k)return;
    if(l==r)
    {
        seg[id].ac=stat;
        seg[id].s=val;
        return;
    }
    int 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(int id,int l,int r,int x)
{
    long long res=0;
    if(x<=0)return 0;
    if(seg[id].ac<=x)
    {
        return seg[id].s;
    }
    int 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;
}
int n,st,d,a[nax],pl[nax],attraction[nax];
long long dp[nax];
int ab(int a)
{
    if(a<0)return -a;else return a;
}
void dc1(int lo,int hi,int lovl,int hivl)
{
    if(lo>hi)return;
    int mid=(lo+hi)>>1,x=lovl;
    for(int i=mid;i<=hi;i++)
    {
        update(1,1,n,pl[i],a[i],1);
    }
    for(int i=lovl;i<=hivl;i++)
    {
        int tmpd=d-min(ab(st-mid),ab(i-st))-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(int i=mid;i<=hi;i++)
    {
        update(1,1,n,pl[i],0,0);
    }
    for(int i=x;i<=hivl;i++)update(1,1,n,pl[i],0,0);
    dc1(mid+1,hi,x,hivl);
    for(int i=mid;i<=hi;i++)
    {
        update(1,1,n,pl[i],a[i],1);
    }
    for(int i=lovl;i<=x;i++)update(1,1,n,pl[i],0,0);
    dc1(lo,mid-1,lovl,x);
}
long long findMaxAttraction(int N, int start, int days, int attraction[])
{
    long long ans=0;
    pair<int,int>b[nax];
    n=N;st=start;d=days;
    st++;
    for(int i=1;i<=n;i++)
    {
        a[i]=attraction[i-1];
        b[i].first=-a[i];
        b[i].second=i;
        dp[i]=-inf;
    }
    build(1,1,n);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        pl[b[i].second]=i;
    }
    dc1(1,st,st,n);
    for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
    return ans;
}

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