Submission #91813

#	Time	Username	Problem	Language	Result	Execution time	Memory
91813		SamAnd	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	157 ms	41772 KiB

route

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <deque>
using namespace std;
const int N=1000006;
struct ban
{
    int l,r,x;
};

int n;
long long k;
int a[N],ll[N],rr[N];
long long b[N];
deque<ban> q;
int mm(int i)
{
    if(i==1)
        return n;
    return i-1;
}
int pp(int i)
{
    if(i==n)
        return 1;
    return i+1;
}
int main()
{
    //freopen("g.in","r",stdin);
    //freopen("g.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    ///////////////////////////////
    for(int i=1;i<=n;++i)
    {
        ban t;
        t.x=a[i];
        t.l=i;
        for(;a[i]==t.x && i<=n;++i)
            t.r=i;
        --i;
        ll[t.r]=t.l;
        rr[t.l]=t.r;
        q.push_back(t);
    }
    if(a[1]==a[n])
    {
        ban t1=q.front(),t2=q.back();
        q.pop_back();
        q.pop_front();
        ban t;
        t.x=a[1];
        t.l=t2.l;
        t.r=t1.r;
        ll[t.r]=t.l;
        rr[t.l]=t.r;
        q.push_back(t);
    }
    while(!q.empty())
    {
        ban t=q.front();
        q.pop_front();
        int l=t.l;
        int r=t.r;
        int x=t.x;
        ban h;
        if(l<=r)
        {
            if(!(a[l]<a[mm(l)] && a[r]<a[pp(r)]))
                continue;
            h.x=min(a[mm(l)],a[pp(r)]);
            b[r-l+1]+=(h.x-x);
        }
        else
        {
            if(!(a[l]<a[mm(l)] && a[r]<a[pp(r)]))
                continue;
            h.x=min(a[mm(l)],a[pp(r)]);
            b[r+n-l+1]+=(h.x-x);
        }
        h.l=l;
        h.r=r;
        if(h.x==a[mm(l)])
        {
            h.l=ll[mm(l)];
        }
        if(h.x==a[pp(r)])
        {
            h.r=rr[pp(r)];
        }
        ll[h.r]=h.l;
        rr[h.l]=h.r;
        q.push_front(h);
    }
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        long long x=(i*b[i]);
        if(k>=x)
        {
            k-=x;
            ans+=b[i];
        }
        else
        {
            ans+=(k/i);
            k=0;
            break;
        }
    }
    cout<<ans*2<<endl;
    return 0;
}

• Subtask 1: 100 / 100