結果

問題 No.1211 円環はお断り
ユーザー kusaf_
提出日時 2024-09-08 00:57:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,726 ms / 2,000 ms
コード長 3,386 bytes
コンパイル時間 3,385 ms
コンパイル使用メモリ 261,260 KB
実行使用メモリ 62,640 KB
最終ジャッジ日時 2024-09-08 00:57:47
合計ジャッジ時間 34,165 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename S, auto op> struct Doubling {
  static_assert(is_convertible_v<decltype(op), function<S(S, S)>>);

 private:
  int n = 0;
  vector<vector<ll>> nxts;
  vector<vector<S>> prds;

  void build() {
    vector<ll> nxt(n);
    vector<S> prd(n);
    for(int i = 0; i < n; i++) {
      if(int j = nxts.back()[i]; in(j)) {
        nxt[i] = nxts.back()[j];
        prd[i] = op(prds.back()[i], prds.back()[j]);
      }
      else {
        nxt[i] = j;
        prd[i] = prds.back()[i];
      }
    }
    nxts.emplace_back(move(nxt));
    prds.emplace_back(move(prd));
  }
  inline bool in(int i) const noexcept { return 0 <= i && i < n; }
  int pow_next(int s, int d) {
    assert(in(s));
    while(ssize(nxts) <= d) { build(); }
    return nxts[d][s];
  }
  const S &pow_prod(int s, int d) {
    assert(in(s));
    while(ssize(nxts) <= d) { build(); }
    return prds[d][s];
  }

 public:
  Doubling() = default;
  Doubling(const vector<ll> &g, vector<S> &w): n(ssize(g)), nxts(1, g), prds(1, w) { assert(ssize(g) == ssize(w)); }
  int next(int s, ll k) {
    for(int d = 0; k > 0 && in(s); d++, k >>= 1) {
      if(k & 1) { s = pow_next(s, d); }
    }
    return s;
  }
  S prod(int s, ll len) {
    assert(in(s));
    assert(len > 0);
    int d = 0;
    while(!(len & 1)) {
      d++;
      len /= 2;
    }
    S r = pow_prod(s, d);
    s = pow_next(s, d);
    for(++d, len /= 2; len && in(s); d++, len /= 2) {
      if(len & 1) {
        r = op(r, pow_prod(s, d));
        s = pow_next(s, d);
      }
    }
    return r;
  }
  int distance(int s, int l, int r) {
    assert(in(s));
    if(s <= l || r <= s) { return 0; }
    int d = 0;
    while(l < pow_next(s, d) && pow_next(s, d) < r) {
      if((1 << d) >= n) { return -1; }
      d++;
    }
    int ret = 0, cur = s;
    for(--d; d >= 0; d--) {
      if(int nxt = pow_next(cur, d); l < nxt && nxt < r) {
        ret += 1 << d;
        cur = nxt;
      }
    }
    return ret + 1;
  }
  template<typename F> ll maxlen(const int s, F f, const int maxd = 60) {
    assert(in(s));
    int d = 0;
    while(d <= maxd && f(pow_prod(s, d))) {
      if(!in(pow_next(s, d))) { return 1LL << maxd; }
      d++;
    }
    if(d > maxd) { return 1LL << maxd; }
    d--;
    int cur = pow_next(s, d);
    ll len = 1LL << d;
    S p = pow_prod(s, d);
    for(int e = d - 1; e >= 0; e--) {
      if(S nxtp = op(p, pow_prod(cur, e)); f(nxtp)) {
        swap(p, nxtp);
        cur = pow_next(cur, e);
        len += 1LL << e;
      }
    }
    return len;
  }
};

using S = ll;
S op(S l, S r) { return 0; }

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

  ll N, K;
  cin >> N >> K;

  vector<ll> A(N);
  for(auto &i : A) { cin >> i; }
  for(ll i = 0; i < N; i++) { A.emplace_back(A[i]); }

  vector<ll> S{0};
  for(auto &i : A) { S.emplace_back(S.back() + i); }

  vector<ll> _(2 * N, 0);
  for(ll L = 0, R = 1e15;;) {
    if(R - L <= 1) {
      cout << L << "\n";
      break;
    }
    ll M = (L + R) / 2;
    bool flag = [&]() -> bool {
      vector<ll> nx(2 * N, -1);
      for(ll i = 0; i < 2 * N; i++) { nx[i] = ranges::lower_bound(S, S[i] + M) - S.begin(); }
      Doubling<ll, op> D(nx, _);
      for(ll i = 0; i < N; i++) {
        if(D.next(i, K) <= i + N) { return true; }
      }
      return false;
    }();
    flag ? L = M : R = M;
  }
}
0