Submission #13364

#	Time	Username	Problem	Language	Result	Execution time	Memory
13364		baneling100	Mountain Trek Route (IZhO12_route)	C++98	45 / 100	240 ms	17612 KiB

route

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define N_MAX 1000000

using namespace std;

typedef pair <int,int> ppair;
priority_queue <ppair,vector<ppair>,greater<ppair> > PQ;
int N, K, Ans;
int M, Block[N_MAX+1], Size[N_MAX+1];
int Left[N_MAX+1], Right[N_MAX+1];

int main(void) {

    int i, inp, t1, t2, h1, h2;

    scanf("%d %d",&N,&K);
    for(i=1 ; i<=N ; i++) {
        scanf("%d",&inp);
        if(Block[M]==inp) Size[M]++;
        else Block[++M]=inp, Size[M]=1;
    }
    if(M>1 && Block[1]==Block[M]) Size[1]+=Size[M--];
    if(M==1) {
        printf("0");
        return 0;
    }
    if(Block[M]>Block[1]) Left [1]=M;
    if(Block[1]<Block[2]) Right[1]=2;
    if(Left[1] && Right[1]) PQ.push(make_pair(Size[1],1));
    for(i=2 ; i<=M-1 ; i++) {
        if(Block[i-1]>Block[i  ]) Left [i]=i-1;
        if(Block[i  ]<Block[i+1]) Right[i]=i+1;
        if(Left[i] && Right[i]) PQ.push(make_pair(Size[i],i));
    }
    if(Block[M-1]>Block[M]) Left [M]=M-1;
    if(Block[M  ]<Block[1]) Right[M]=1;
    if(Left[M] && Right[M]) PQ.push(make_pair(Size[M],M));
    while(!PQ.empty()) {
        t1=PQ.top().first, t2=PQ.top().second, PQ.pop();
        h1=K/t1;
        h2=min(Block[Left[t2]],Block[Right[t2]])-Block[t2];
        if(h1<h2) {
            Ans+=h1<<1;
            break;
        }
        else {
            Ans+=h2<<1;
            K-=t1*h2;
            if(Block[Left[t2]]<Block[Right[t2]]) {
                Size [Left[t2]]+=Size [t2];
                Right[Left[t2]] =Right[t2];
                if(Left[Left[t2]]) PQ.push(make_pair(Size[Left[t2]],Left[t2]));
            }
            else if(Block[Left[t2]]>Block[Right[t2]]) {
                Size[Right[t2]]+=Size[t2];
                Left[Right[t2]] =Left[t2];
                if(Right[Right[t2]]) PQ.push(make_pair(Size[Right[t2]],Right[t2]));
            }
            else {
                inp=Size[Left[t2]];
                Size [Left[t2]]+=Size[t2]+Size[Right[t2]];
                Right[Left[t2]] =Right[Right[t2]];
                Size[Right[t2]]+=Size[t2]+inp;
                Left[Right[t2]] =Left[Left[t2]];
                if(Left[Left[t2]] && Right[Left[t2]]) PQ.push(make_pair(Size[Left[t2]],Left[t2]));
            }
        }
    }
    printf("%d",Ans);
    return 0;
}

• Subtask 1: 45 / 100