Cod sursă (job #547306)

#include<fstream>
#define MOD 1000003
using namespace std;
ifstream fi("sam.in");
ofstream fo("sam.out");
typedef struct idk{int x,y;} IDK;
IDK AI[2][400005],nr;
int n,i,rez,lmax,a;
 
void upd(int t, int nod, int st, int dr, int u, IDK val)
{
    if(st==dr)
    {
        if(AI[t][nod].y==val.y)
            AI[t][nod].x=(AI[t][nod].x+val.x)%MOD;
        if(AI[t][nod].y<val.y)
        {
            AI[t][nod].x=val.x;
            AI[t][nod].y=val.y;
        }
        return;
    }
    int mij=(st+dr)/2;
    if(u<=mij)
        upd(t,2*nod,st,mij,u,val);
    else
        upd(t,2*nod+1,mij+1,dr,u,val);
    AI[t][nod]=AI[t][2*nod];
    if(AI[t][nod].y==AI[t][2*nod+1].y)
        AI[t][nod].x=(AI[t][nod].x+AI[t][2*nod+1].x)%MOD;
    if(AI[t][nod].y<AI[t][2*nod+1].y)
    {
        AI[t][nod].x=AI[t][2*nod+1].x;
        AI[t][nod].y=AI[t][2*nod+1].y;
    }
}
 
void qry(int t, int nod, int st, int dr, int lft, int rgt)
{
    if(lft>rgt)
        return;
    if(lft<=st && dr<=rgt)
    {
        if(AI[t][nod].y==nr.y)
            nr.x=(AI[t][nod].x+nr.x)%MOD;
        if(AI[t][nod].y>nr.y)
        {
            nr.x=AI[t][nod].x;
            nr.y=AI[t][nod].y;
        }
        return;
    }
    int mij=(st+dr)/2;
    if(lft<=mij)
        qry(t,2*nod,st,mij,lft,rgt);
    if(rgt>mij)
        qry(t,2*nod+1,mij+1,dr,lft,rgt);
}
 
int main()
{
    fi>>n;
    rez=1;
    lmax=1;
    fi>>a;
    upd(0,1,1,n,a,{1,2});
    upd(1,1,1,n,a,{1,2});
    for(i=2; i<=n; i++)
    {
        fi>>a;
        nr={1,1};
        qry(0,1,1,n,a,n);
        if(nr.y>lmax)
        {
            lmax=nr.y;
            rez=0;
        }
        if(nr.y==lmax)
            rez=(rez+nr.x)%MOD;
        nr.y++;
        upd(1,1,1,n,a,nr);
        nr={1,1};
        qry(1,1,1,n,1,a-1);
        if(nr.y>lmax)
        {
            lmax=nr.y;
            rez=0;
        }
        if(nr.y==lmax)
            rez=(rez+nr.x)%MOD;
        nr.y++;
        upd(0,1,1,n,a,nr);
    }
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}