Cod sursă (job #720018)

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define mod 1000003
using namespace std;
const int maxn=1e5+5;
pair<int,int> A[2][4*maxn],nr;
int n,ans,maxim,a;
 
pair<int,int> comb(pair<int,int> a, pair<int,int> b){
    pair<int,int> ans={0,0};
    ans.S=max(a.S,b.S);
    if(ans.S==a.S)
        ans.F=(ans.F+a.F)%mod;
    if(ans.S==b.S)
        ans.F=(ans.F+b.F)%mod;
    return ans;
}
 
void update(int t,int node,int l,int r,int u,pair<int,int> val){
    if(l==r){
        A[t][node]=comb(A[t][node],val);
        return;
    }
    int mid=(l+r)/2;
    if(u<=mid) update(t,2*node,l,mid,u,val);
    else{
    	update(t,2*node+1,mid+1,r,u,val);	
	}
    A[t][node]=comb(A[t][2*node],A[t][2*node+1]);
}
 
void query(int t,int node,int l,int r,int ql,int qr){
    if(l>r) return;
    if(ql<=l&&r<=qr){
        nr=comb(nr,A[t][node]);
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid){
    	query(t,2*node,l,mid,ql,qr);	
	}
    if(qr>mid){
    	query(t,2*node+1,mid+1,r,ql,qr);	
	}
}
int main(){
	ifstream cin("sam.in");
	ofstream cout("sam.out");
    cin >> n;
    ans=1;
    maxim=1;
    cin >> a;
    update(0,1,1,n,a,{1,2});
    update(1,1,1,n,a,{1,2});
    for(int i=2;i<=n;i++){
        cin >> a;
        nr={1,1};
        query(0,1,1,n,a,n);
        if(nr.S>maxim){
            maxim=nr.S;
            ans=0;
        }
        if(nr.S==maxim)ans=(ans+nr.F)%mod;
        nr.S++;
        update(1,1,1,n,a,nr);
        nr={1,1};
        query(1,1,1,n,1,a-1);
        if(nr.S>maxim){
            maxim=nr.S;
            ans=0;
        }
        if(nr.S==maxim)ans=(ans+nr.F)%mod;
        nr.S++;
        update(0,1,1,n,a,nr);
    }
	cout << ans << endl;
    return 0;
}