結果

問題 No.1435 Mmm......
ユーザー CyanmondCyanmond
提出日時 2021-03-19 22:49:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 635 ms / 2,000 ms
コード長 5,736 bytes
コンパイル時間 6,650 ms
コンパイル使用メモリ 310,256 KB
実行使用メモリ 20,888 KB
最終ジャッジ日時 2024-11-19 00:12:19
合計ジャッジ時間 18,763 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 381 ms
9,776 KB
testcase_07 AC 480 ms
10,848 KB
testcase_08 AC 573 ms
12,128 KB
testcase_09 AC 520 ms
11,452 KB
testcase_10 AC 442 ms
10,364 KB
testcase_11 AC 432 ms
10,180 KB
testcase_12 AC 395 ms
9,732 KB
testcase_13 AC 385 ms
9,676 KB
testcase_14 AC 277 ms
7,996 KB
testcase_15 AC 600 ms
12,396 KB
testcase_16 AC 479 ms
10,968 KB
testcase_17 AC 319 ms
8,504 KB
testcase_18 AC 606 ms
12,440 KB
testcase_19 AC 418 ms
10,136 KB
testcase_20 AC 547 ms
11,708 KB
testcase_21 AC 531 ms
20,888 KB
testcase_22 AC 553 ms
18,096 KB
testcase_23 AC 614 ms
12,460 KB
testcase_24 AC 625 ms
12,592 KB
testcase_25 AC 635 ms
12,588 KB
testcase_26 AC 600 ms
12,588 KB
testcase_27 AC 594 ms
12,592 KB
権限があれば一括ダウンロードができます

ソースコード

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