Cod sursă (job #547096)

#include<fstream>
using namespace std;
ifstream  f("sam.in"); 
ofstream g("sam.out");
int m=1000003;
int n,r,i,sens,a[100009],x[100009],b[2][100009],c[100009];
void cobor_sau_urc(int sens, int p)
{   int i,j,k;
    for(k=x[p-1];k<=x[p];k++) c[k]=b[1-sens][k];
    i=x[p]; j=x[p]+1;
    while((x[p-1]<i) && (j<=x[p+1]))
        if((x[p-1]<i-1) && ((a[i-1]>a[j] && sens==0) || (a[i-1]<a[j] && sens==1)))
        {
            c[i-1]=(c[i-1]+c[i])%m; i--;
        } 
        else
        {
            b[sens][j]=(b[sens][j]+c[i])%m; j++;
        }
    for(k=x[p-1];k<=x[p];k++) c[k]=b[1-sens][k];
    i=x[p]; j=x[p+2]-1;
    while((a[i]<a[j]&&sens==0)||(a[i]>a[j]&&sens==1)) j--;
    while((x[p-1]<i) && (x[p+1]<j))
        if((x[p-1]<i-1) && ((a[i-1]>a[j] && sens==0)||(a[i-1]<a[j] && sens==1)))
            c[i-1]=(c[i-1]+c[i])%m,i--;
        else
            b[sens][j]=(b[sens][j]+c[i])%m,j--;
    for(k=x[p];k<=x[p+1];k++) c[k]=b[1-sens][k];
    i=x[p]+1; j=x[p+2]-1;
    while((a[i]<a[j]&&sens==0)||(a[i]>a[j]&&sens==1)) j--;
    while((i<x[p+1]) && (x[p+1]<=j))
        if((i+1<x[p+1]) && ((a[i+1]>a[j] && sens==0)||(a[i+1]<a[j] && sens==1)))
        {
            c[i+1]=(c[i+1]+c[i])%m;
            b[sens][i+1]=(b[sens][i+1]+c[i])%m; i++;
        }
        else
            b[sens][j]=(b[sens][j]+c[i])%m,j--;  
}
int main()
{   f>>n;
    for(i=1;i<=n;i++) f>>a[i];
    if(a[1]<a[2]) a[0]=n+1; else a[0]=0;
    if(a[n-1]<a[n])a[n+1]=-1; else a[n+1]=n+2;
    x[0]=-1; x[1]=0;
    r=1;
    for(i=1;i<=n;i++)
        if((a[i-1]<a[i] && a[i]>a[i+1])||(a[i-1]>a[i] && a[i]<a[i+1])) x[++r]=i;
    x[r+1]=n+1; x[r+2]=n+2;
    if(a[0]>a[1]) sens=1; else sens=0;
    b[sens][0]=1;
    for(i=1;i<=r;i++) {sens=1-sens; cobor_sau_urc(sens,i);}
    g<<b[sens][n+1]<<"\n"; g.close(); return 0;
}