Submission #13377

#	Time	Username	Problem	Language	Result	Execution time	Memory
13377		dohyun0324	Mountain Trek Route (IZhO12_route)	C++98	95 / 100	503 ms	9800 KiB

route

#include<stdio.h>
#include<queue>
using namespace std;
typedef pair<int,int> ppair;
int len,n,k,a[1000010],pos[1000010];
long long dap,t;
priority_queue<ppair,vector<ppair>,greater<ppair> >q;
int main()
{
    int i,p,s1,s2;
    scanf("%d %d",&n,&k);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    a[0]=a[n+1]=2147483647;
    for(i=1;i<=n;i++)
    {
        if(a[i]!=a[i-1]) p=i;
        if(a[i]!=a[i+1])
        {
            pos[p]=i; pos[i]=p;
            if(a[i+1]>a[i] && a[p-1]>a[p])
            {
                if(p==1 || i==n) continue;
                q.push(make_pair(i-p+1,p));
            }
        }
    }
    if(a[n]==a[1])
    {
        if(a[pos[n]-1]>a[n] && a[n]<a[pos[1]+1]) q.push(make_pair(n-pos[n]+1+pos[1],pos[n]));
        pos[pos[n]]=pos[1];
    }
    else if(a[n]>a[1] && a[1]<a[2]) q.push(make_pair(pos[1],1));
    else if(a[n]<a[1] && a[n]<a[n-1]) q.push(make_pair(n-pos[n]+1,pos[n]));
    while(1)
    {
        a[0]=a[n]; a[n+1]=a[1]; pos[0]=pos[n]; pos[n+1]=pos[1];
        len=q.top().first; p=q.top().second;
        q.pop();
        if(s1==s2 || len>=n) break;
        if(a[p-1]<a[pos[p]+1])
        {
            t+=len*(a[p-1]-a[p]);
            if(t>=k)
            {
                t-=len*(a[p-1]-a[p]);
                dap+=(k-t)/len;
                break;
            }
            dap+=a[p-1]-a[p];
            s1=pos[p-1]; s2=pos[p];
            pos[s1]=s2; pos[s2]=s1;
            a[s2]=a[p-1];
            if(a[s1-1]>a[s2] && a[s2]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
            if(a[s1-1]>a[s2] && a[s2]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
        }
        else if(a[p-1]>a[pos[p]+1])
        {
            t+=len*(a[pos[p]+1]-a[p]);
            if(t>=k)
            {
                t-=len*(a[pos[p]+1]-a[p]);
                dap+=(k-t)/len;
                break;
            }
            dap+=a[pos[p]+1]-a[p];
            s1=p; s2=pos[pos[p]+1];
            a[s1]=a[pos[p]+1];
            pos[s1]=s2; pos[s2]=s1;
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
        }
        else
        {
            t+=len*(a[pos[p]+1]-a[p]);
            if(t>=k)
            {
                t-=len*(a[pos[p]+1]-a[p]);
                dap+=(k-t)/len;
                break;
            }
            dap+=a[pos[p]+1]-a[p];
            s1=pos[p-1]; s2=pos[pos[p]+1];
            pos[s1]=s2; pos[s2]=s1;
            a[s1]=a[pos[p]+1];
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
        }
    }
    printf("%lld",dap*2);
    return 0;
}

• Subtask 1: 95 / 100