Cod sursă (job #543194)

#include<fstream>
#define MOD 1000003
#define x first
#define y second
using namespace std;
ifstream fi("sam.in");
ofstream fo("sam.out");
pair<int,int> AI[2][400005],nr;
int n,A[100005],i,rez,lmax;
 
pair<int,int> comb(pair<int,int> a, pair<int,int> b)
{
    pair<int,int> rez={0,0};
    rez.y=max(a.y,b.y);
    if(rez.y==a.y)
        rez.x=(rez.x+a.x)%MOD;
    if(rez.y==b.y)
        rez.x=(rez.x+b.x)%MOD;
    return rez;
}
 
void upd(int t, int nod, int st, int dr, int u, pair<int,int> val)
{
    if(st==dr)
    {
        AI[t][nod]=comb(AI[t][nod],val);
        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]=comb(AI[t][2*nod],AI[t][2*nod+1]);
}
 
void qry(int t, int nod, int st, int dr, int lft, int rgt)
{
    if(st>dr)
        return;
    if(lft<=st && dr<=rgt)
    {
        nr=comb(nr,AI[t][nod]);
        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;
    for(i=1; i<=n; i++)
        fi>>A[i];
    rez=1;
    lmax=1;
    upd(0,1,1,n,A[1],{1,2});
    upd(1,1,1,n,A[1],{1,2});
    for(i=2; i<=n; i++)
    {
        nr={1,1};
        qry(0,1,1,n,A[i],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[i],nr);
        nr={1,1};
        qry(1,1,1,n,1,A[i]-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[i],nr);
    }
    
    
    
    
    
    
    
    
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
    
    
    
    
    
    
    
    
}