結果

問題 No.1435 Mmm......
ユーザー m_tsubasam_tsubasa
提出日時 2021-03-19 22:57:07
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,516 ms / 2,000 ms
コード長 4,950 bytes
コンパイル時間 2,658 ms
コンパイル使用メモリ 210,944 KB
実行使用メモリ 8,876 KB
最終ジャッジ日時 2023-08-12 03:54:03
合計ジャッジ時間 29,719 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 891 ms
8,068 KB
testcase_07 AC 1,127 ms
8,280 KB
testcase_08 AC 1,362 ms
8,720 KB
testcase_09 AC 1,219 ms
8,876 KB
testcase_10 AC 1,028 ms
8,344 KB
testcase_11 AC 1,011 ms
8,424 KB
testcase_12 AC 944 ms
8,292 KB
testcase_13 AC 915 ms
8,448 KB
testcase_14 AC 649 ms
5,956 KB
testcase_15 AC 1,398 ms
8,848 KB
testcase_16 AC 1,140 ms
8,348 KB
testcase_17 AC 752 ms
6,204 KB
testcase_18 AC 1,451 ms
8,664 KB
testcase_19 AC 996 ms
8,344 KB
testcase_20 AC 1,277 ms
8,644 KB
testcase_21 AC 1,022 ms
8,552 KB
testcase_22 AC 985 ms
8,704 KB
testcase_23 AC 1,492 ms
8,596 KB
testcase_24 AC 1,500 ms
8,624 KB
testcase_25 AC 1,487 ms
8,604 KB
testcase_26 AC 1,514 ms
8,620 KB
testcase_27 AC 1,516 ms
8,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// 0-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }
  SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {
    int _n = v.size();
    init(v.size());
    for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1;
    while (n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while (k >>= 1) dat[k] = f(dat[k << 1], dat[(k << 1) | 1]);
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
  // require: func(unit) == false
  // min left: st <= res && func(seg.query(st,res + 1))
  template <typename C>
  int find_left(int st, C &func, T &acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(acc, dat[k]);
      return func(acc) ? l : -1;
    }
    int mid = (l + r) >> 1;
    if (mid <= st) return find_left(st, func, acc, (k << 1) | 1, mid, r);
    if (st <= l && !func(f(acc, dat[k]))) {
      acc = f(acc, dat[k]);
      return -1;
    }
    int nres = find_left(st, func, acc, (k << 1), l, mid);
    if (~nres) return nres;
    return find_left(st, func, acc, (k << 1) | 1, mid, r);
  }
  template <typename C>
  int find_left(int st, C &func) {
    T acc = unit;
    return find_left(st, func, acc, 1, 0, n);
  }

  // max right: res <= st && func(seg.query(res - 1,st))
  template <typename C>
  int find_right(int st, C &func, T &acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(dat[k], acc);
      return func(acc) ? r : -1;
    }
    int mid = (l + r) >> 1;
    if (st <= mid) return find_right(st, func, acc, k << 1, l, mid);
    if (r <= st && !func(f(dat[k], acc))) {
      acc = f(dat[k], acc);
      return -1;
    }
    int nres = find_right(st, func, acc, (k << 1) | 1, mid, r);
    if (~nres) return nres;
    return find_right(st, func, acc, k << 1, l, mid);
  }
  template <typename C>
  int find_right(int st, C &func) {
    T acc = unit;
    return find_right(st, func, acc, 1, 0, n);
  }
};

int n;
vector<int> a;
SegmentTree<int> segmax, segcnt;

long long solve();
int calcneighbor(int id, bool isleft);
int calclen(int lid, int rid, int lim, bool isleft);

int main() {
  cin >> n;
  a.resize(n);
  for (auto &p : a) cin >> p;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0;
  vector<int> id(n);
  iota(id.begin(), id.end(), 0);
  sort(id.begin(), id.end(), [](int l, int r) { return a[l] < a[r]; });
  {
    auto segmaxf = [](int l, int r) { return max(l, r); };
    segmax = SegmentTree<int>(a, segmaxf, 0);
    auto segcntf = [](int l, int r) { return l + r; };
    segcnt = SegmentTree<int>(n, segcntf, 0);
  }
  for (auto nid : id) {
    int lid = calcneighbor(nid, 1), rid = calcneighbor(nid, 0);
    if (lid >= 0) {  // use left min
      int llid = calcneighbor(lid, 1), lim = a[nid] + a[lid];
      res += 1LL * max(calclen(llid, nid, lim, 1) - (nid - lid), 0) *
             calclen(nid, rid, lim, 0);
    }
    if (rid < n) {  // use right min
      int rrid = calcneighbor(rid, 0), lim = a[nid] + a[rid];
      res += 1LL * calclen(lid, nid, lim, 1) *
             max(calclen(nid, rrid, lim, 0) - (rid - nid), 0);
    }
    segcnt.update(nid, 1);
  }
  return res;
}

int calcneighbor(int id, bool isleft) {
  if (isleft) {
    if (segcnt.query(0, id)) {  // search left id
      int l = 0, r = id;
      while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (segcnt.query(mid, id))
          l = mid;
        else
          r = mid;
      }
      assert(segcnt.query(l, l + 1));
      return l;
    } else
      return -1;
  }
  if (segcnt.query(++id, n)) {  // search right id
    int l = id, r = n;
    while (r - l > 1) {
      int mid = (l + r) >> 1;
      if (segcnt.query(id, mid))
        r = mid;
      else
        l = mid;
    }
    assert(segcnt.query(l, l + 1));
    return l;
  }
  return n;
}

int calclen(int lid, int rid, int lim, bool isleft) {
  if (isleft) {
    ++lid, ++rid;
    if (segmax.query(lid, rid) <= lim) return rid - lid;
    int l = lid, r = rid;
    while (r - l > 1) {
      int mid = (l + r) >> 1;
      if (segmax.query(mid, rid) <= lim)
        r = mid;
      else
        l = mid;
    }
    return rid - r;
  }
  if (segmax.query(lid, rid) <= lim) return rid - lid;
  int l = lid, r = rid;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (segmax.query(lid, mid) <= lim)
      l = mid;
    else
      r = mid;
  }
  return l - lid;
}
0