結果
問題 | No.2281 K → K-1 01 Flip |
ユーザー | tokusakurai |
提出日時 | 2023-04-22 00:02:40 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 12,818 bytes |
コンパイル時間 | 2,958 ms |
コンパイル使用メモリ | 206,128 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-11-06 17:20:35 |
合計ジャッジ時間 | 11,407 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 11 ms
5,376 KB |
testcase_02 | AC | 85 ms
5,248 KB |
testcase_03 | AC | 92 ms
6,784 KB |
testcase_04 | AC | 24 ms
5,248 KB |
testcase_05 | AC | 40 ms
5,504 KB |
testcase_06 | AC | 74 ms
5,248 KB |
testcase_07 | AC | 24 ms
6,784 KB |
testcase_08 | AC | 59 ms
6,784 KB |
testcase_09 | AC | 85 ms
5,248 KB |
testcase_10 | AC | 68 ms
5,248 KB |
testcase_11 | AC | 28 ms
5,248 KB |
testcase_12 | AC | 25 ms
6,912 KB |
testcase_13 | AC | 84 ms
5,248 KB |
testcase_14 | AC | 45 ms
5,504 KB |
testcase_15 | AC | 23 ms
5,248 KB |
testcase_16 | AC | 83 ms
5,248 KB |
testcase_17 | AC | 97 ms
5,376 KB |
testcase_18 | AC | 89 ms
5,248 KB |
testcase_19 | AC | 43 ms
6,528 KB |
testcase_20 | AC | 28 ms
5,248 KB |
testcase_21 | AC | 36 ms
6,656 KB |
testcase_22 | AC | 82 ms
5,248 KB |
testcase_23 | AC | 6 ms
5,248 KB |
testcase_24 | AC | 48 ms
5,248 KB |
testcase_25 | AC | 35 ms
5,248 KB |
testcase_26 | AC | 32 ms
6,528 KB |
testcase_27 | AC | 62 ms
6,912 KB |
testcase_28 | AC | 30 ms
6,784 KB |
testcase_29 | AC | 3 ms
5,248 KB |
testcase_30 | AC | 52 ms
5,248 KB |
testcase_31 | AC | 56 ms
5,376 KB |
testcase_32 | AC | 76 ms
6,528 KB |
testcase_33 | AC | 41 ms
5,248 KB |
testcase_34 | AC | 65 ms
5,248 KB |
testcase_35 | AC | 48 ms
6,912 KB |
testcase_36 | AC | 76 ms
5,248 KB |
testcase_37 | AC | 74 ms
5,248 KB |
testcase_38 | AC | 83 ms
5,248 KB |
testcase_39 | AC | 41 ms
5,248 KB |
testcase_40 | AC | 15 ms
5,248 KB |
testcase_41 | AC | 106 ms
7,040 KB |
testcase_42 | AC | 109 ms
7,168 KB |
testcase_43 | AC | 111 ms
7,040 KB |
testcase_44 | AC | 105 ms
7,040 KB |
testcase_45 | AC | 108 ms
7,040 KB |
testcase_46 | AC | 111 ms
7,168 KB |
testcase_47 | AC | 110 ms
7,040 KB |
testcase_48 | AC | 109 ms
7,040 KB |
testcase_49 | AC | 107 ms
7,168 KB |
testcase_50 | AC | 115 ms
7,040 KB |
testcase_51 | AC | 109 ms
7,168 KB |
testcase_52 | AC | 108 ms
7,168 KB |
testcase_53 | AC | 109 ms
7,168 KB |
testcase_54 | AC | 113 ms
7,040 KB |
testcase_55 | AC | 110 ms
7,040 KB |
testcase_56 | AC | 109 ms
7,040 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)#define per(i, n) for (int i = (n)-1; i >= 0; i--)#define rep2(i, l, r) for (int i = (l); i < (r); i++)#define per2(i, l, r) for (int i = (r)-1; i >= (l); i--)#define each(e, v) for (auto &e : v)#define MM << " " <<#define pb push_back#define eb emplace_back#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>using minheap = priority_queue<T, vector<T>, greater<T>>;template <typename T>using maxheap = priority_queue<T>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}int popcount(int x) { return __builtin_popcount(x); }int popcount(ll x) { return __builtin_popcountll(x); }int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }int botbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }int botbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');if (v.empty()) cout << '\n';}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}template <typename T>void reorder(vector<T> &a, const vector<int> &ord) {int n = a.size();vector<T> b(n);for (int i = 0; i < n; i++) b[i] = a[ord[i]];swap(a, b);}template <typename T>T floor(T x, T y) {assert(y != 0);if (y < 0) x = -x, y = -y;return (x >= 0 ? x / y : (x - y + 1) / y);}template <typename T>T ceil(T x, T y) {assert(y != 0);if (y < 0) x = -x, y = -y;return (x >= 0 ? (x + y - 1) / y : x / y);}template <typename S, typename T>pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first + q.first, p.second + q.second);}template <typename S, typename T>pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first - q.first, p.second - q.second);}template <typename S, typename T>istream &operator>>(istream &is, pair<S, T> &p) {S a;T b;is >> a >> b;p = make_pair(a, b);return is;}template <typename S, typename T>ostream &operator<<(ostream &os, const pair<S, T> &p) {return os << p.first << ' ' << p.second;}struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;const int inf = (1 << 30) - 1;const ll INF = (1LL << 60) - 1;// const int MOD = 1000000007;const int MOD = 998244353;template <typename Monoid>struct Segment_Tree {using M = typename Monoid::V;int n, m;vector<M> seg;// f(f(a,b),c) = f(a,f(b,c)), f(e1,a) = f(a,e1) = aSegment_Tree(const vector<M> &v) : n(v.size()) {m = 1;while (m < n) m <<= 1;seg.assign(2 * m, Monoid::id);copy(begin(v), end(v), begin(seg) + m);for (int i = m - 1; i > 0; i--) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]);}Segment_Tree(int n, const M &x) : Segment_Tree(vector<M>(n, x)) {}void update(int i, const M &x, bool apply = false) {seg[i + m] = apply ? Monoid::merge(seg[i + m], x) : x;i += m;while (i >>= 1) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]);}M query(int l, int r) const {l = max(l, 0), r = min(r, n);M L = Monoid::id, R = Monoid::id;l += m, r += m;while (l < r) {if (l & 1) L = Monoid::merge(L, seg[l++]);if (r & 1) R = Monoid::merge(seg[--r], R);l >>= 1, r >>= 1;}return Monoid::merge(L, R);}M operator[](int i) const { return seg[i + m]; }template <typename C>int find_subtree(int i, const C &check, M &x, int type) const {while (i < m) {M nxt = type ? Monoid::merge(seg[2 * i + type], x) : Monoid::merge(x, seg[2 * i + type]);if (check(nxt)) {i = 2 * i + type;} else {x = nxt;i = 2 * i + (type ^ 1);}}return i - m;}// check(区間 [l,r] での演算結果) を満たす最小の r (存在しなければ n)template <typename C>int find_first(int l, const C &check) const {M L = Monoid::id;int a = l + m, b = 2 * m;while (a < b) {if (a & 1) {M nxt = Monoid::merge(L, seg[a]);if (check(nxt)) return find_subtree(a, check, L, 0);L = nxt;a++;}a >>= 1, b >>= 1;}return n;}// check((区間 [l,r) での演算結果)) を満たす最大の l (存在しなければ -1)template <typename C>int find_last(int r, const C &check) const {M R = Monoid::id;int a = m, b = r + m;while (a < b) {if ((b & 1) || a == 1) {M nxt = Monoid::merge(seg[--b], R);if (check(nxt)) return find_subtree(b, check, R, 1);R = nxt;}a >>= 1, b >>= 1;}return -1;}};// sumtemplate <typename T>struct Plus_Monoid {using V = T;static constexpr V merge(V l, V r) { return l + r; };static const V id;};template <typename T>const T Plus_Monoid<T>::id = 0;// mintemplate <typename T>struct Min_Monoid {using V = T;static constexpr V merge(V l, V r) { return min(l, r); };static const V id;};template <typename T>const T Min_Monoid<T>::id = numeric_limits<T>::max();// maxtemplate <typename T>struct Max_Monoid {using V = T;static constexpr V merge(V l, V r) { return max(l, r); };static const V id;};template <typename T>const T Max_Monoid<T>::id = numeric_limits<T>::min();// 代入template <typename T>struct Update_Monoid {using V = T;static constexpr V merge(V l, V r) {if (l == id) return r;if (r == id) return l;return r;}static const V id;};template <typename T>const T Update_Monoid<T>::id = numeric_limits<T>::max();// min count (T:最大値の型、S:個数の型)template <typename T, typename S>struct Min_Count_Monoid {using V = pair<T, S>;static constexpr V merge(V l, V r) {if (l.first < r.first) return l;if (l.first > r.first) return r;return V(l.first, l.second + r.second);}static const V id;};template <typename T, typename S>const pair<T, S> Min_Count_Monoid<T, S>::id = make_pair(numeric_limits<T>::max(), 0);// max count (T:最大値の型、S:個数の型)template <typename T, typename S>struct Max_Count_Monoid {using V = pair<T, S>;static constexpr V merge(V l, V r) {if (l.first > r.first) return l;if (l.first < r.first) return r;return V(l.first, l.second + r.second);}static const V id;};template <typename T, typename S>const pair<T, S> Max_Count_Monoid<T, S>::id = make_pair(numeric_limits<T>::min(), 0);// 一次関数 ax+b の合成 (左から順に作用)template <typename T>struct Affine_Monoid {using V = pair<T, T>;static constexpr V merge(V l, V r) { return V(l.first * r.first, l.second * r.first + r.second); };static const V id;};template <typename T>const pair<T, T> Affine_Monoid<T>::id = make_pair(1, 0);// モノイドの直積template <typename Monoid_1, typename Monoid_2>struct Cartesian_Product_Monoid {using V1 = typename Monoid_1::V;using V2 = typename Monoid_2::V;using V = pair<V1, V2>;static constexpr V merge(V l, V r) { return V(Monoid_1::merge(l.first, r.first), Monoid_2::merge(l.second, r.second)); }static const V id;};template <typename Monoid_1, typename Monoid_2>const pair<typename Monoid_1::V, typename Monoid_2::V> Cartesian_Product_Monoid<Monoid_1, Monoid_2>::id = make_pair(Monoid_1::id, Monoid_2::id);// range add range mintemplate <typename T>struct Min_Plus_Acted_Monoid {using Monoid = Min_Monoid<T>;using Operator = Plus_Monoid<T>;using M = T;using O = T;static constexpr M merge(M l, O r) { return l + r; };};// range add range maxtemplate <typename T>struct Max_Plus_Acted_Monoid {using Monoid = Max_Monoid<T>;using Operator = Plus_Monoid<T>;using M = T;using O = T;static constexpr M merge(M l, O r) { return l + r; };};// range add range min count (T:最小値の型、S:個数の型)template <typename T, typename S>struct Min_Count_Add_Acted_Monoid {using Monoid = Min_Count_Monoid<T, S>;using Operator = Plus_Monoid<T>;using M = pair<T, S>;using O = T;static constexpr M merge(M l, O r) { return make_pair(l.first + r, l.second); };};// range add range max count (T:最大値の型、S:個数の型)template <typename T, typename S>struct Max_Count_Add_Acted_Monoid {using Monoid = Max_Count_Monoid<T, S>;using Operator = Plus_Monoid<T>;using M = pair<T, S>;using O = T;static constexpr M merge(M l, O r) { return make_pair(l.first + r, l.second); };};// range add range sumtemplate <typename T>struct Plus_Plus_Monoid {using Monoid = Cartesian_Product_Monoid<Plus_Monoid<T>, Plus_Monoid<int>>;using Operator = Plus_Monoid<T>;using M = pair<T, int>;using O = T;static constexpr M merge(M l, O r) { return M(l.first + r * l.second, l.second); }};// range update range sumtemplate <typename T>struct Plus_Update_Monoid {using Monoid = Cartesian_Product_Monoid<Plus_Monoid<T>, Plus_Monoid<int>>;using Operator = Update_Monoid<T>;using M = pair<T, int>;using O = T;static constexpr M merge(M l, O r) { return M(r * l.second, l.second); }};// range update range mintemplate <typename T>struct Min_Update_Monoid {using Monoid = Min_Monoid<T>;using Operator = Update_Monoid<T>;using M = T;using O = T;static constexpr M merge(M l, M r) { return r == Operator::id ? l : r; }};// range update range maxtemplate <typename T>struct Max_Update_Monoid {using Monoid = Max_Monoid<T>;using Operator = Update_Monoid<T>;using M = T;using O = T;static constexpr M merge(M l, M r) { return r == Operator::id ? l : r; }};// range affine range sumtemplate <typename T>struct Plus_Affine_Acted_Monoid {using Monoid = Cartesian_Product_Monoid<Plus_Monoid<T>, Plus_Monoid<T>>;using Operator = Affine_Monoid<T>;using M = pair<T, T>;using O = pair<T, T>;static constexpr M merge(M l, O r) { return M(r.first * l.first + r.second * l.second, l.second); };};void solve() {int N, Q;string S;cin >> N >> Q >> S;vector<int> a(N);a[N - 1] = 1;per(i, N - 1) {a[i] = 1;if (S[i] == S[i + 1]) a[i] = a[i + 1] + 1;}vector<int> s(N + 1, 0);rep(i, N) {s[i + 1] = s[i];if (S[i] == '0') s[i + 1]++;if (S[i] == '1') s[i + 1]--;}// print(a), print(s);Segment_Tree<Max_Monoid<int>> seg(a);while (Q--) {int L, R, K;cin >> L >> R >> K;L--;if (seg.query(L, R - K + 1) < K) {cout << R - L << '\n';} else {int t = s[R] - s[L];t %= (2 * K - 1);// cout << "! " << t << '\n';if (t < 0) t += 2 * K - 1;if (t >= K) t -= 2 * K - 1;cout << 2 * (K - 1) - abs(t) << '\n';}}}int main() {int T = 1;// cin >> T;while (T--) solve();}