Submission #49802680

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void O(const T &x) { cout << x << '\n'; }
template <typename T, typename... W> inline void O(const T &x, const W &...b) {
  cout << x << ' ';
  O(b...);
}
template <typename T> inline void rd(T &x) { cin >> x; }
template <typename T, typename... W> inline void rd(T &x, W &...b) {
  cin >> x;
  rd(b...);
}
#ifndef MISAKA
#define err(...)
#else
#define err(...) fprintf(stderr, __VA_ARGS__)
#endif
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef long double dbl;
typedef pair<int, int> pii;
typedef uniform_int_distribution<int> r32;
typedef uniform_int_distribution<i64> r64;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define shuf(L, R) shuffle((L), (R), rng)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define FOR(i, j, k) for (int i = (j); i <= (k); ++i)
#define ROF(i, j, k) for (int i = (k); i >= (j); --i)
template <typename T> inline void ckmin(T &a, const T &b) { a = min(a, b); }
template <typename T> inline void ckmax(T &a, const T &b) { a = max(a, b); }
//#define IOFILE "filename"
//#define MULTI
const int N = 1e5+5;
int a[N];
int p[N][11], q[N][11];
int r[N];

inline void sol() {
  int n;
  rd(n);
  for (int i = 1; i <= n; ++i) r[i] = n+1;
  for (int j = 1; j <= n; ++j) for (int i = 1; i < 11; ++i) q[j][i] = n+1;
  for (int i = 1; i <= n; ++i) {
    rd(a[i]);
    p[i][a[i]] = q[i][a[i]] = i;
  }
  for (int i = 2; i <= n; ++i) for (int j = 1; j < 11; ++j) ckmax(p[i][j], p[i-1][j]);
  for (int i = n-1; i > 0; --i) for (int j = 1; j < 11; ++j) ckmin(q[i][j], q[i+1][j]);
  for (int i = 2; i < n; ++i) for (int j = 1; j < 11; ++j) {
    int k = 2*a[i]-j;
    if (k < 1 || k > 10) continue;
    ckmin(r[p[i-1][j]], q[i+1][k]);
  }
  for (int i = n-1; i > 0; --i) ckmin(r[i], r[i+1]);
  i64 ans = 0;
  for (int i = 1; i <= n; ++i) ans += n+1-r[i];
  O(ans);
}

int main() {
#ifndef MISAKA
#ifdef IOFILE
  freopen(IOFILE ".in", "r", stdin);
  freopen(IOFILE ".out", "w", stdout);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
#endif
#ifdef MULTI
  int T;
  cin >> T;
  while (T--)
#endif
    sol();
  return 0;
}

Submission Info

Judge Result