結果

問題 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0