Cod sursă (job #547257)

#include <fstream>

#include <algorithm>

using namespace std;

ifstream fin("sam.in");
ofstream fout("sam.out");

const int MOD = 1000003;
const int Dim = 100002;
int N;
int A[Dim], B[Dim];
int D[Dim][2], S[Dim][2];

void SOLVE(int i, int j) {
  int q, viz[10], k1, ma[10][10],n;
  if (!q && !viz[i]) {
    fout << i << " ";
    k1++;
  }
  q = 1;
  viz[i] = true;
  if (!viz[j])
    fout << j << " ";
  viz[j] = true;
  ma[i][j] = 0;
  ma[j][i] = 0;

  for (int h = 1; h <= n; h++) {
    if (ma[j][h])
      SOLVE(j, h);
  }
}
void AddLow(int & x, int p, int v) {
  if (p == 0) {
    ++x;
    if (x >= MOD) x -= MOD;
    return;
  }
  if (A[B[p]] > v) return;

  int lim1 = (p == 1 ? 1 : B[p - 1] + 1);
  int lim2 = (p == B[0] ? N : B[p + 1] - 1);
  if (lim1 > lim2) return;

  int p2, b1 = B[p], b2 = B[p];
  for (p2 = (1 << 16); p2; p2 >>= 1)
    if (b1 - p2 >= lim1 && A[b1 - p2] < v)
      b1 -= p2;
  for (p2 = (1 << 16); p2; p2 >>= 1)
    if (b2 + p2 <= lim2 && A[b2 + p2] < v)
      b2 += p2;

  x += S[b2][1] - S[b1 - 1][1];
  if (x >= MOD) x -= MOD;
  if (x < 0) x += MOD;
}

void AddHigh(int & x, int p, int v) {
  if (p == 0) {
    ++x;
    if (x >= MOD) x -= MOD;
    return;
  }
  if (A[B[p]] < v) return;

  int lim1 = (p == 1 ? 1 : B[p - 1] + 1);
  int lim2 = (p == B[0] ? N : B[p + 1] - 1);
  if (lim1 > lim2) return;

  int p2, b1 = B[p], b2 = B[p];
  for (p2 = (1 << 16); p2; p2 >>= 1)
    if (b1 - p2 >= lim1 && A[b1 - p2] > v)
      b1 -= p2;
  for (p2 = (1 << 16); p2; p2 >>= 1)
    if (b2 + p2 <= lim2 && A[b2 + p2] > v)
      b2 += p2;

  x += S[b2][0] - S[b1 - 1][0];
  if (x >= MOD) x -= MOD;
  if (x < 0) x += MOD;
}

int main() {

  fin >> N;
  for (int i = 1; i <= N; ++i)
    fin >> A[i];

  B[++B[0]] = 1;
  for (int i = 2; i <= N - 1; ++i)
    if (A[i] < A[i - 1] && A[i] < A[i + 1])
      B[++B[0]] = i;
    else if (A[i] > A[i - 1] && A[i] > A[i + 1])
    B[++B[0]] = i;

  B[++B[0]] = N;
  D[1][0] = 1;
  S[1][0] = 1;
  D[1][1] = 1;
  S[1][1] = 1;

  int p = 1;
  for (int i = 2; i <= N; ++i) {
    if (i > B[p])
      ++p;

    bool up = false;
    if (i == B[p] && A[i] > A[i - 1]) up = true;
    if (i != B[p] && A[i] < A[i + 1]) up = true;

    // 0 - vine din mai mic
    if (up) AddLow(D[i][0], p - 1, A[i]);
    else AddLow(D[i][0], p - 2, A[i]);

    // 1 - vine din mai mare
    if (up) AddHigh(D[i][1], p - 2, A[i]);
    else AddHigh(D[i][1], p - 1, A[i]);

    S[i][0] = S[i - 1][0] + D[i][0];
    if (S[i][0] >= MOD) S[i][0] -= MOD;
    S[i][1] = S[i - 1][1] + D[i][1];
    if (S[i][1] >= MOD) S[i][1] -= MOD;
  }

  int sol = 0;
  if (A[N] > A[N - 1]) {
    sol = D[N][0];
    for (int i = N - 1; i >= 2 && A[i] > A[i - 1]; --i) {
      sol += D[i][0];
      if (sol >= MOD) sol -= MOD;
    }
  } else {
    sol = D[N][1];
    for (int i = N - 1; i >= 2 && A[i] < A[i - 1]; --i) {
      sol += D[i][1];
      if (sol >= MOD) sol -= MOD;
    }
  }

  fout << sol << '\n';

  fin.close();
  fout.close();
}