結果

問題 No.1435 Mmm......
コンテスト
ユーザー ZOI-dayo
提出日時 2025-10-30 11:46:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 485 ms / 2,000 ms
コード長 2,484 bytes
コンパイル時間 3,534 ms
コンパイル使用メモリ 286,220 KB
実行使用メモリ 17,184 KB
最終ジャッジ日時 2025-10-30 11:46:18
合計ジャッジ時間 15,298 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

//@yukicoder 1435

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T>
using vec = vector<T>;
template <class T>
using vv = vec<vec<T>>;
template <class T>
using vvv = vv<vec<T>>;
template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for (ll i = 0; i < (r); i++)
#define reps(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep(i, l, r) for (ll i = (r)-1; i >= l; i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
template <typename T>
bool chmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}

const ll INF = 4e18;

struct Node {
  ll mn1, mn2, mx;
};

#define T Node
#define e \
  Node { INF, INF, -INF }

ll second_min(Node a, Node b) {
  vl x = {a.mn1, a.mn2, b.mn1, b.mn2};
  sort(all(x));
  return x[1];
}

#define op(a, b) \
  Node { min(a.mn1, b.mn1), second_min(a, (b)), max(a.mx, b.mx) }

struct SegTree {
  int n = 1;
  vec<T> v;

  // 構築 O(N log N)
  SegTree(int N) {
    while (n < N) n *= 2;
    v.assign(n * 2, e);
  }

  // 一点更新 O(log N)
  // i : [0, n)
  void update(int i, T a) {
    i += n;
    v[i] = a;
    while (i > 1) {
      i /= 2;
      v[i] = op(v[i * 2], v[i * 2 + 1]);
    }
  }

  // 区間総積取得 O(log N)
  // l : [0, n), r : [1, n], l < r
  T query(int l, int r, int x = 1, int lx = 0, int rx = -1) {
    if (rx < 0) rx = n;
    if (rx <= l || r <= lx) return e;
    if (l <= lx && rx <= r) return v[x];
    int m = (lx + rx) / 2;
    T lv = query(l, r, x * 2, lx, m), rv = query(l, r, x * 2 + 1, m, rx);
    return op(lv, rv);
  }

  int max_right(auto f) {
    if (!f(e)) return 0;
    if (f(v[1])) return n;
    T s = e;
    int i = 1;
    while (i < n) {
      int l = i << 1;
      T t = op(s, v[l]);
      if (f(t)) s = t, i = l + 1;
      else i = l;
    }
    return i - n;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) cin >> a[i];

  SegTree seg(n);
  rep(i, n) { seg.update(i, Node{a[i], INF, a[i]}); }

  ll ans = 0;
  rep(l, n) {
    ll r = seg.max_right([](Node x) -> bool {
      if (x.mn2 >= INF / 2) return true;
      return x.mx <= x.mn1 + x.mn2;
    });
    chmin(r, n);
    ans += max(0LL, r - l - 1);
    seg.update(l, e);
  }

  cout << ans << '\n';
  return 0;
}
0