Cod sursă (job #543068)

#include <fstream>
#include <algorithm>
 using namespace std;
ifstream in ( "sam.in"  );
ofstream out( "sam.out" );
 
const int DIM = 3 + 5;
const int MOD = 1e6 + 3;
 
pair<int, int> sgt[2][DIM * 4];
 
inline int f( int x ) {
    return ( x < MOD ) ? x : ( x - MOD ); }
 
pair<int, int> update( int k, int n, int l, int r, int p, pair<int, int> v ) {
    if( l > r || l > p || p > r ) {
        return sgt[k][n]; }
    if( l == p && r == p ) {
        sgt[k][n] = v; return sgt[k][n]; }
    int m = l + ( r - l ) / 2;
    pair<int, int> ans1 = update( k, n * 2, l, m, p, v );
    pair<int, int> ans2 = update( k, n * 2 + 1, m + 1, r, p, v );
    sgt[k][n].first = max( ans1.first, ans2.first ); sgt[k][n].second = 0;
    if( sgt[k][n].first == ans1.first ) {
        sgt[k][n].second = f( sgt[k][n].second + ans1.second ); }
    if( sgt[k][n].first == ans2.first ) {
        sgt[k][n].second = f( sgt[k][n].second + ans2.second ); }
    return sgt[k][n]; }
 
pair<int, int> query( int k, int n, int l, int r, int st, int fi ) {
    if( l > r || l > fi || st > r ) {
        return make_pair( 0, 0 ); }
    if( st <= l && r <= fi ) {
        return sgt[k][n]; }
    int m = l + ( r - l ) / 2; pair<int, int> ans;
    pair<int, int> ans1 = query( k, n * 2, l, m, st, fi );
    pair<int, int> ans2 = query( k, n * 2 + 1, m + 1, r, st, fi );
    ans.first = max( ans1.first, ans2.first ); ans.second = 0;
    if( ans.first == ans1.first ) {
        ans.second = f( ans.second + ans1.second ); }
    if( ans.first == ans2.first ) {
        ans.second = f( ans.second + ans2.second ); }
    return ans; }
 
int main() {
    ios::sync_with_stdio( false );
    int n, ans = 0, maxim = 0; in >> n;
    for( int i = 1; i <= n; i ++ ) {
        pair<int, int> ans1, ans2; int x; in >> x;
        ans1 = query( 1, 1, 1, n, x + 1, n );
        if( ans1.second == 0 ) { ans1.second ++; }
        ans1.first ++; update( 0, 1, 1, n, x, ans1 );
        ans2 = query( 0, 1, 1, n, 1, x - 1 );
        if( ans2.second == 0 ) { ans2.second ++; }
        ans2.first ++; update( 1, 1, 1, n, x, ans2 ); }
    maxim = max( sgt[0][1].first, sgt[1][1].first );
    if( maxim == sgt[0][1].first ) { ans = f( ans + sgt[0][1].second ); }
    if( maxim == sgt[1][1].first ) { ans = f( ans + sgt[1][1].second ); }
    out << ans << endl;
    return 0; }