Cod sursă (job #547047)

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int mod=1000003;
string s;
struct arb
{
    int a,m;
}aib[2][100005];
int best[2],modes[2];
int n,i,idx,x,num,ch;
inline int lbit(int x)
{
    return (((x^(x-1))&x));
}
void compute(int poz,int w)
{
    for(idx=poz;idx>0;idx-=lbit(idx))
    {
        if(aib[w][idx].a>best[1^w])
            best[1^w]=aib[w][idx].a,modes[1^w]=0;
        if(aib[w][idx].a==best[1^w])
        {
            modes[1^w]+=aib[w][idx].m;
            if(modes[1^w]>=mod) modes[1^w]-=mod;
        }
    }
}
void update(int poz,int w)
{
    for(idx=poz;idx<=n;idx+=lbit(idx))
    {
        if(best[w]>aib[w][idx].a)
            aib[w][idx].a=best[w],aib[w][idx].m=0;
        if(aib[w][idx].a==best[w])
        {
            aib[w][idx].m+=modes[w];
            if(aib[w][idx].m>=mod) aib[w][idx].m-=mod;
        }
    }
}
int getnum()
{
    num=0;
   while(s[ch]>='0'&&s[ch]<='9')
     num=num*10+s[ch]-'0',ch++;
     ch++;
   return num;
}
int main()
{
    ifstream f("sam.in");
    ofstream g("sam.out");
    f>>n;getline(f,s);
    getline(f,s);
    for(i=1;i<=n;i++)
    {
        x=getnum();
        best[0]=best[1]=modes[0]=modes[1]=0;
        compute(x,0);
        compute(n-x+1,1);
        best[0]++,best[1]++;
        if(best[0]==1) modes[0]=1;
        if(best[1]==1) modes[1]=1;
        update(x,0);
        update(n-x+1,1);
    }
    best[0]=best[1]=modes[0]=modes[1]=0;
    compute(n,0);
    compute(n,1);
    if(best[0]>best[1])
        modes[1]=0;
    if(best[1]>best[0])
        modes[0]=0;
    g<<(modes[0]+modes[1])%mod;
    return 0;
}