結果

問題 No.1435 Mmm......
ユーザー CyanmondCyanmond
提出日時 2021-03-19 22:49:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,736 bytes
コンパイル時間 8,216 ms
コンパイル使用メモリ 244,376 KB
最終ジャッジ日時 2025-01-19 19:06:00
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from main.cpp:6:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Bvector_base<std::allocator<bool> >::_Bvector_impl::~_Bvector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long unsigned int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:67,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_bvector.h:590:14: note: called from here
  590 |       struct _Bvector_impl
      |              ^~~~~~~~~~~~~

ソースコード

diff # 

#pragma region library
#if defined(__GNUC__) && !defined(__llvm__) && !defined(__clang__)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#endif
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif
#pragma region
#define whole(f, x, ...) ([&](auto& v) { return (f)(std::begin(v), std::end(v), ## __VA_ARGS__); })(x)

#define rep32(i, l, r) for (int i = (int)(l); (i) < (int)(r); ++(i))
#define rep64(i, l, r) for (long long i = (long long)(l); i < (long long)(r); ++(i))
#define revrep32(i, r, l) for (int i = (int)(r); (i) >= (int)(l); --(i))
#define revrep64(i, r, l) for (long long i = (long long)(r); i >= (long long)(l); --(i))

using u32 = unsigned int;
using usize = size_t;
using index_t = size_t;
using i64 = long long;
using u64 = unsigned long long;
constexpr size_t operator "" _uz(unsigned long long v) { return static_cast<size_t>(v); }

template <class T> using Heap = std::priority_queue<T>;
template <class T> using RevHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T, class F> using SHeap = std::priority_queue<T, std::vector<T>, F>;

constexpr int dx[] = { 1, 0, -1, 0 };
constexpr int dy[] = { 0, 1, 0, -1 };

constexpr int INF32 = 1001001001;
constexpr long long INF64 = 1501501501501501501ll;

constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;

#pragma endregion

template <class T, class U>
constexpr bool chmin(T& a, const U& b) noexcept {
  return a > b ? a = b, true : false;
}
template <class T, class U>
constexpr bool chmax(T& a, const U& b) noexcept {
  return a < b ? a = b, true : false;
}
template <class type = size_t, class T> constexpr type len(const T& v) noexcept { return (type)(v.size()); }

template <class T, class... Ts> std::vector<std::tuple<T&, Ts&...>> zip(std::vector<T>& t, std::vector<Ts>&... ts) {
  const size_t n = t.size();
  std::vector<std::tuple<T&, Ts&...>> res;
  for (size_t i = 0; i < n; i++) res.emplace_back(t[i], ts[i]...);
  return res;
}
template <class T, class... Ts> std::vector<std::tuple<size_t, T&, Ts&...>> idzip(std::vector<T>& t, std::vector<Ts>&... ts) {
  const size_t n = t.size();
  std::vector<std::tuple<size_t, T&, Ts&...>> res;
  for (size_t i = 0; i < n; i++) res.emplace_back(i, t[i], ts[i]...);
  return res;
}

namespace nlb {
  template <class T, class U> constexpr T Pow(T A, U B) noexcept {
    T res = 1;
    while (B) {
      if (B & 1) { res *= A; }
      A *= A; B >>= 1;
    }
    return res;
  }

  template <class T, class U, class M = int> constexpr T modpow(T A, U B, M MOD = 1000000007) noexcept {
    A %= MOD;
    T res = 1;
    while (B) {
      if (B & 1) { res *= A; res %= MOD; }
      A *= A; A %= MOD;
      B >>= 1;
    }
    return res;
  }

  template <class T, class M = int> constexpr T inverse(T A, const M MOD = 1000000007) noexcept {
    T B = MOD, U = 1, V = 0;
    while (B) {
      T t = A / B;
      A -= t * B; std::swap(A, B);
      U -= t * V; std::swap(U, V);
    }
    U %= MOD;
    return U < 0 ? U += MOD, U : U;
  }

  template <class T> constexpr bool isprime(const T N) noexcept {
    if (N == 1) return false;
    for (T i = 2; i * i <= N; i++) if (N % i == 0) return false;
    return true;
  }

  inline std::tuple<long long, long long, long long> extgcd(const long long a, const long long b) {
    if (b == 0) return { a,1,0 };
    long long g, x, y;
    std::tie(g, x, y) = extgcd(b, a % b);
    return std::make_tuple(g, y, x - a / b * y);
  }

  inline std::pair<long long, long long> Chinese_Rem(const std::vector<long long>& b, const std::vector<long long>& m) {
    long long r = 0, M = 1;
    for (int i = 0; i < (int)b.size(); ++i) {
      long long p, q, d;
      std::tie(d, p, q) = extgcd(M, m[i]);
      if ((b[i] - r) % d != 0) return std::make_pair(0, -1);
      long long tmp = (b[i] - r) / d * p % (m[i] / d);
      r += M * tmp;
      M *= m[i] / d;
    }
    return std::make_pair((r % M + M) % M, M);
  }
}

class ProCon_all_init {
  static constexpr bool float_fixed = true;
  static constexpr int ios_perc = 15;
  static constexpr bool ios_fast = true;
  static constexpr bool auto_flush = false;
public:
  ProCon_all_init() {
    if (ios_fast) { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios::sync_with_stdio(false); }
    if (float_fixed) { std::cout << std::fixed << std::setprecision(ios_perc); }
    if (auto_flush) { std::cout << std::unitbuf; }
  }
} ProCon_;
#pragma endregion

int main(void) {
  // input
  i64 N; std::cin >> N;
  std::vector<i64> A(N);
  for (auto& el : A) std::cin >> el;

  // solve
  // 分割統治法をします
  // 中心を含む or 含まない
  // l が中心にちかづくするにつれて r は離れる

  std::function<i64(std::vector<i64>&)> solver = [&](std::vector<i64> v)->i64 {
    int n = len(v);
    if (n < 2) return 0;
    if (n == 2) return 1;

    int half = n / 2;
    int half2 = n - half;
    std::vector<i64> lvec, rvec;
    rep32(i, 0, half) lvec.emplace_back(v[i]);
    rep32(i, half, n) rvec.emplace_back(v[i]);
    std::multiset<i64> S;
    for (auto& el : lvec) S.emplace(el);
    i64 R = 0;
    i64 Answer = 0;
    rep32(i, 0, half) { // 尺取り
      while (len(S) < 2 && R < half2) {
        S.emplace(rvec[R++]);
      }
      while (R < half2) {
        chmax(R, 0);
        S.emplace(rvec[R]);
        auto itr1 = S.begin();
        auto itr2 = itr1; itr2++;
        auto itr3 = S.end(); itr3--;
        if (!(*itr1 + *itr2 >= *itr3)) {
          S.erase(S.find(rvec[R]));
          break;
        }
        R++;
      }
      Answer += R;
      S.erase(S.find(lvec[i]));
    }
    return Answer + solver(lvec) + solver(rvec);
  };

  std::cout << solver(A) << std::endl;
}
0