結果
問題 |
No.2281 K → K-1 01 Flip
|
ユーザー |
![]() |
提出日時 | 2023-04-21 22:20:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 618 ms / 2,000 ms |
コード長 | 1,276 bytes |
コンパイル時間 | 3,622 ms |
コンパイル使用メモリ | 176,052 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-11-06 15:51:22 |
合計ジャッジ時間 | 27,750 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 56 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/segtree> using namespace std; int op(int x, int y){ return max(x, y); } int e(){ return 0; } int main(){ int N, Q; cin >> N >> Q; string S; cin >> S; vector<int> sum(N + 1); sum[0] = 0; for (int i = 0; i < N; i++){ if (S[i] == '0'){ sum[i + 1] = sum[i] + 1; } else { sum[i + 1] = sum[i] - 1; } } set<int> st; st.insert(0); st.insert(N); for (int i = 1; i < N; i++){ if (S[i] != S[i - 1]){ st.insert(i); } } vector<int> c(N, 1); for (int i = 1; i < N; i++){ if (S[i] == S[i - 1]){ c[i] = c[i - 1] + 1; } else { c[i] = 1; } } atcoder::segtree<int, op, e> ST(c); for (int i = 0; i < Q; i++){ int L, R, K; cin >> L >> R >> K; L--; auto itr = st.lower_bound(L); bool ok = false; if (*itr >= R){ if (R - L >= K){ ok = true; } } else { if (*itr - L >= K){ ok = true; } if (ST.prod(*itr, R) >= K){ ok = true; } } if (!ok){ cout << R - L << endl; } else { int s = sum[R] - sum[L]; s %= K * 2 - 1; s += K * 2 - 1; s %= K * 2 - 1; s = min(s, K * 2 - 1 - s); cout << K * 2 - 2 - s << endl; } } }