Submission #429240

#	Time	Username	Problem	Language	Result	Execution time	Memory
429240		TLP39	Holiday (IOI14_holiday)	C++14	100 / 100	1098 ms	6616 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int n,d;
int start;
int a[100010];
map<int,int> mp;
auto it=mp.begin();
ll tot_max=0,k=0;
ll res;
int st,ed,pos,p2;

void movel(int x,int dl)
{
    while(st>x)
    {
        st--;
        mp[a[st]]++;
        k-=dl;
        if(a[st]>(it->first))
        {
            pos++;
            tot_max+=a[st];
        }
        while(k<pos)
        {
            pos--;
            tot_max-=(it->first);
            p2--;
            if(!p2)
            {
                it++;
                p2=(it->second);
            }
        }
        while(k>pos)
        {
            if(it==mp.begin() && (it->second)==p2) break;
            pos++;
            p2++;
            if(p2>(it->second))
            {
                it--;
                p2=1;
            }
            tot_max+=(it->first);
        }
    }
    while(st<x)
    {
        k+=dl;
        if(a[st]>(it->first) || (a[st]==(it->first) && p2==(it->second)))
        {
            pos--;
            tot_max-=a[st];
            if(a[st]==(it->first))
            {
                p2--;
                if(!p2)
                {
                    if(it==mp.begin())
                    {
                        it++;
                        p2=(it->second);
                    }
                    else
                    {
                        it--;
                        pos++;
                        p2=1;
                        tot_max+=(it->first);
                    }
                }
            }
        }
        mp[a[st]]--;
        if(!mp[a[st]]) mp.erase(a[st]);
        while(k<pos)
        {
            pos--;
            tot_max-=(it->first);
            p2--;
            if(!p2)
            {
                it++;
                p2=(it->second);
            }
        }
        while(k>pos)
        {
            if(it==mp.begin() && (it->second)==p2) break;
            pos++;
            p2++;
            if(p2>(it->second))
            {
                it--;
                p2=1;
            }
            tot_max+=(it->first);
        }
        st++;
    }
}

void mover(int y,int dr)
{
    while(ed<y)
    {
        ed++;
        k-=dr;
        mp[a[ed]]++;
        if(a[ed]>(it->first))
        {
            pos++;
            tot_max+=a[ed];
        }
        while(k<pos)
        {
            pos--;
            tot_max-=(it->first);
            p2--;
            if(!p2)
            {
                it++;
                p2=(it->second);
            }
        }
        while(k>pos)
        {
            if(it==mp.begin() && (it->second)==p2) break;
            pos++;
            p2++;
            if(p2>(it->second))
            {
                it--;
                p2=1;
            }
            tot_max+=(it->first);
        }
    }
    while(ed>y)
    {
        k+=dr;
        if(a[ed]>(it->first) || (a[ed]==(it->first) && p2==(it->second)))
        {
            pos--;
            tot_max-=a[ed];
            if(a[ed]==(it->first))
            {
                p2--;
                if(!p2)
                {
                    if(it==mp.begin())
                    {
                        it++;
                        p2=(it->second);
                    }
                    else
                    {
                        it--;
                        pos++;
                        p2=1;
                        tot_max+=(it->first);
                    }
                }
            }
        }
        mp[a[ed]]--;
        if(!mp[a[ed]]) mp.erase(a[ed]);
        while(k<pos)
        {
            pos--;
            tot_max-=(it->first);
            p2--;
            if(!p2)
            {
                it++;
                p2=(it->second);
            }
        }
        while(k>pos)
        {
            if(it==mp.begin() && (it->second)==p2) break;
            pos++;
            p2++;
            if(p2>(it->second))
            {
                it--;
                p2=1;
            }
            tot_max+=(it->first);
        }
        ed--;
    }

}

int test(int s,int l,int r,int dl,int dr)
{
    if(l>r) return -1;
    if(dl*(start-s)+dr*(l-start)>=d) return -1;
    int ans=l;
    ll temp_res;
    if(l<=ed)
    {
        mover(l,dr);
        movel(s,dl);
    }
    else
    {
        movel(s,dl);
        mover(l,dr);
    }
    temp_res=tot_max;
    for(int i=l+1;i<=r;i++)
    {
        if(dl*(start-s)+dr*(i-start)>=d) break;
        mover(i,dr);
        if(tot_max>temp_res)
        {
            temp_res=tot_max;
            ans=i;
        }
    }
    res=max(res,temp_res);
    return ans;
}

void alltest(int l1,int r1,int l2,int r2,int dl,int dr)
{
    if(l1>r1 || l2>r2) return;
    int temp;
    if(l1==r1)
    {
        temp=test(l1,l2,r2,dl,dr);
        return;
    }
    int mid=(l1+r1)>>1;
    temp=test(mid,l2,r2,dl,dr);
    alltest(l1,mid-1,l2,temp,dl,dr);
    alltest(mid+1,r1,temp,r2,dl,dr);
}

long long int findMaxAttraction(int N, int sta, int D, int attraction[]) {
    if(!D) return 0ll;
    if(D==1) return (ll)attraction[sta];
    n=N;
    d=D;
    start=sta;
    for(int i=0;i<n;i++) a[i]=attraction[i];
    st=sta;
    ed=sta;
    k=d;
    tot_max=res=(ll)a[sta];
    mp[a[st]]=1;
    pos=1;
    p2=1;
    it=mp.begin();
    alltest(max(0,sta-d+1),sta,sta,n-1,1,2);
    st=sta;
    ed=sta;
    k=d;
    tot_max=(ll)a[sta];
    auto it3=mp.begin();
    for(auto it2=mp.begin();it2!=mp.end();)
    {
        it3=it2;
        it2++;
        mp.erase(it3);
    }
    mp[a[st]]=1;
    pos=1;
    p2=1;
    it=mp.begin();
    alltest(max(0,sta-(d-1)/2),sta,sta,n-1,2,1);
    return res;
}

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