Cod sursă (job #785388)

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000003
int b[100003],c[100003],v[100003],dp[2][100003];
void solve(int dir,int p) {
    int i,j,k;
    for(k=b[p-1]; k<=b[p]; k++)
        c[k]=dp[1-dir][k];
    i=b[p];
    j=b[p]+1;
    while((b[p-1]<i)&&(j<=b[p+1])) {
        if((b[p-1]<i-1) &&((v[i-1]>v[j]&&dir==0)||(v[i-1]<v[j]&&dir==1))) {
            c[i-1]=(c[i-1]+c[i])%MOD;
            i--;
        } else {
            dp[dir][j]=(dp[dir][j]+c[i])%MOD;
            j++;
        }
    }
    for(k=b[p-1]; k<=b[p]; k++)
        c[k]=dp[1-dir][k];
    i=b[p];
    j=b[p+2]-1;
    while((v[i]<v[j]&&dir==0)||(v[i]>v[j]&&dir==1))
        j--;
    while((b[p-1]<i)&&(b[p+1]<j)) {
        if((b[p-1]<i-1) && ((v[i-1]>v[j]&&dir==0)||(v[i-1]<v[j]&&dir==1))) {
            c[i-1]=(c[i-1]+c[i])%MOD;
            i--;
        } else {
            dp[dir][j]=(dp[dir][j]+c[i])%MOD;
            j--;
        }
    }
    for(k=b[p]; k<=b[p+1]; k++)
        c[k]=dp[1-dir][k];
    i=b[p]+1;
    j=b[p+2]-1;
    while((v[i]<v[j]&&dir==0)||(v[i]>v[j]&&dir==1))
        j--;
    while((i<b[p+1])&&(b[p+1]<=j)) {
        if((i+1<b[p+1])&&((v[i+1]>v[j]&&dir==0)||(v[i+1]<v[j]&&dir==1))) {
            c[i+1]=(c[i+1]+c[i])%MOD;
            dp[dir][i+1]=(dp[dir][i+1]+c[i])%MOD;
            i++;
        } else {
            dp[dir][j]=(dp[dir][j]+c[i])%MOD;
            j--;
        }
    }
}
int main() {
    FILE *fin,*fout;
    int n,i,nr,dir;
    fin=fopen("sam.in","r");
    fscanf(fin,"%d",&n);
    for(i=1; i<=n; i++) {
        fscanf(fin,"%d",&v[i]);
    }
    if(v[1]<v[2]) {
        v[0]=n+1;
    }
    v[n+1]=n+2;
    if(v[n-1]<v[n]) {
        v[n+1]=-1;
    }
    b[0]=-1;
    nr=1;
    for(i=1; i<=n; i++) {
        if((v[i]>v[i-1]&&v[i]>v[i+1])||(v[i]<v[i-1]&&v[i]<v[i+1])) {
            nr++;
            b[nr]=i;
        }
    }
    b[nr+1]=n+1;
    b[nr+2]=b[nr+1]+1;
    dir=0;
    if(v[0]>v[1]) {
        dir=1;
    }
    dp[dir][0]=1;
    for(i=0; i<nr; i++) {
        dir=1-dir;
        solve(dir,i+1);
    }
    fout=fopen("sam.out","w");
    fprintf(fout,"%d",dp[dir][n+1]);
    fclose(fout);
    return 0;
}