#631969 (C++17) No.1435 Mmm......

提出ソース

結果

問題	No.1435 Mmm......
ユーザー	m_tsubasa
提出日時	2021-03-19 22:57:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,581 ms / 2,000 ms
コード長	4,950 bytes
コンパイル時間	2,471 ms
コンパイル使用メモリ	213,008 KB
実行使用メモリ	8,832 KB
最終ジャッジ日時	2024-11-19 00:29:53
合計ジャッジ時間	30,636 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	947 ms 8,320 KB
testcase_07	AC	1,195 ms 8,576 KB
testcase_08	AC	1,435 ms 8,704 KB
testcase_09	AC	1,306 ms 8,704 KB
testcase_10	AC	1,095 ms 8,448 KB
testcase_11	AC	1,079 ms 8,448 KB
testcase_12	AC	987 ms 8,448 KB
testcase_13	AC	955 ms 8,320 KB
testcase_14	AC	687 ms 6,816 KB
testcase_15	AC	1,488 ms 8,832 KB
testcase_16	AC	1,192 ms 8,448 KB
testcase_17	AC	790 ms 6,816 KB
testcase_18	AC	1,510 ms 8,704 KB
testcase_19	AC	1,040 ms 8,448 KB
testcase_20	AC	1,346 ms 8,576 KB
testcase_21	AC	1,064 ms 8,832 KB
testcase_22	AC	1,023 ms 8,832 KB
testcase_23	AC	1,554 ms 8,704 KB
testcase_24	AC	1,552 ms 8,832 KB
testcase_25	AC	1,560 ms 8,832 KB
testcase_26	AC	1,566 ms 8,832 KB
testcase_27	AC	1,581 ms 8,704 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード