結果
問題 | No.2281 K → K-1 01 Flip |
ユーザー | square1001 |
提出日時 | 2023-04-21 22:30:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 708 ms / 2,000 ms |
コード長 | 2,554 bytes |
コンパイル時間 | 1,048 ms |
コンパイル使用メモリ | 89,256 KB |
実行使用メモリ | 13,072 KB |
最終ジャッジ日時 | 2024-04-24 08:37:53 |
合計ジャッジ時間 | 27,995 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 63 ms
8,448 KB |
testcase_02 | AC | 554 ms
8,320 KB |
testcase_03 | AC | 595 ms
12,660 KB |
testcase_04 | AC | 146 ms
5,760 KB |
testcase_05 | AC | 249 ms
8,448 KB |
testcase_06 | AC | 477 ms
8,320 KB |
testcase_07 | AC | 137 ms
12,660 KB |
testcase_08 | AC | 374 ms
12,792 KB |
testcase_09 | AC | 567 ms
5,888 KB |
testcase_10 | AC | 437 ms
6,016 KB |
testcase_11 | AC | 171 ms
7,936 KB |
testcase_12 | AC | 150 ms
12,640 KB |
testcase_13 | AC | 569 ms
6,016 KB |
testcase_14 | AC | 301 ms
8,448 KB |
testcase_15 | AC | 136 ms
5,376 KB |
testcase_16 | AC | 567 ms
8,320 KB |
testcase_17 | AC | 642 ms
8,320 KB |
testcase_18 | AC | 585 ms
8,192 KB |
testcase_19 | AC | 267 ms
12,644 KB |
testcase_20 | AC | 164 ms
5,760 KB |
testcase_21 | AC | 183 ms
12,416 KB |
testcase_22 | AC | 513 ms
5,760 KB |
testcase_23 | AC | 27 ms
5,376 KB |
testcase_24 | AC | 307 ms
5,376 KB |
testcase_25 | AC | 193 ms
5,376 KB |
testcase_26 | AC | 190 ms
12,416 KB |
testcase_27 | AC | 421 ms
12,788 KB |
testcase_28 | AC | 187 ms
12,648 KB |
testcase_29 | AC | 10 ms
5,376 KB |
testcase_30 | AC | 326 ms
5,376 KB |
testcase_31 | AC | 314 ms
8,320 KB |
testcase_32 | AC | 447 ms
12,416 KB |
testcase_33 | AC | 265 ms
8,192 KB |
testcase_34 | AC | 374 ms
5,376 KB |
testcase_35 | AC | 291 ms
12,792 KB |
testcase_36 | AC | 452 ms
5,376 KB |
testcase_37 | AC | 501 ms
8,064 KB |
testcase_38 | AC | 467 ms
5,376 KB |
testcase_39 | AC | 221 ms
5,504 KB |
testcase_40 | AC | 84 ms
8,320 KB |
testcase_41 | AC | 630 ms
12,800 KB |
testcase_42 | AC | 653 ms
12,892 KB |
testcase_43 | AC | 628 ms
12,800 KB |
testcase_44 | AC | 708 ms
13,072 KB |
testcase_45 | AC | 658 ms
12,816 KB |
testcase_46 | AC | 531 ms
12,672 KB |
testcase_47 | AC | 630 ms
12,672 KB |
testcase_48 | AC | 597 ms
12,800 KB |
testcase_49 | AC | 705 ms
13,068 KB |
testcase_50 | AC | 583 ms
12,672 KB |
testcase_51 | AC | 486 ms
12,672 KB |
testcase_52 | AC | 483 ms
12,672 KB |
testcase_53 | AC | 484 ms
12,672 KB |
testcase_54 | AC | 482 ms
12,672 KB |
testcase_55 | AC | 476 ms
12,672 KB |
testcase_56 | AC | 478 ms
12,544 KB |
ソースコード
#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; const long long INF = 3LL << 60; // range add/max lazy segment tree class lazy_segtree { private: int sz; vector<long long> val; vector<long long> lazy; void push(int k) { if (lazy[k] != 0) { val[k] += lazy[k]; if (k < sz) { lazy[k * 2 + 0] += lazy[k]; lazy[k * 2 + 1] += lazy[k]; } lazy[k] = 0; } } void add(int a, int b, int k, int l, int r, long long x) { push(k); if (a <= l && r <= b) { lazy[k] += x; push(k); return; } if (r <= a || b <= l) { return; } add(a, b, k * 2 + 0, l, (l + r) >> 1, x); add(a, b, k * 2 + 1, (l + r) >> 1, r, x); val[k] = max(val[k * 2 + 0], val[k * 2 + 1]); } long long rangemax(int a, int b, int k, int l, int r) { push(k); if (a <= l && r <= b) { return val[k]; } if (r <= a || b <= l) { return -INF; } long long lc = rangemax(a, b, k * 2 + 0, l, (l + r) >> 1); long long rc = rangemax(a, b, k * 2 + 1, (l + r) >> 1, r); return max(lc, rc); } public: lazy_segtree() : sz(0), val(vector<long long>()), lazy(vector<long long>()) {} lazy_segtree(int n) { sz = 1; while (sz < n) { sz *= 2; } val = vector<long long>(sz * 2, 0); lazy = vector<long long>(sz * 2, 0); } void add(int l, int r, long long x) { add(l, r, 1, 0, sz, x); } long long rangemax(int l, int r) { return rangemax(l, r, 1, 0, sz); } }; int main() { int N, Q; string S; cin >> N >> Q >> S; vector<int> A = { 0 }; for (int i = 1; i < N; i++) { if (S[i - 1] != S[i]) { A.push_back(i); } } A.push_back(N); vector<int> sum(N + 1); for (int i = 0; i < N; i++) { sum[i + 1] = sum[i] + (S[i] == '1' ? 1 : -1); } lazy_segtree seg(N); for (int i = 0; i < int(A.size()) - 1; i++) { seg.add(A[i], A[i + 1], A[i + 1] - A[i]); } for (int i = 0; i < Q; i++) { int L, R, K; cin >> L >> R >> K; L -= 1; int p1 = lower_bound(A.begin(), A.end(), L + 1) - A.begin(); int p2 = lower_bound(A.begin(), A.end(), R) - A.begin(); int maxwidth = 0; if (p1 == p2) { maxwidth = R - L; } else if (p2 - p1 == 1) { maxwidth = max(A[p1] - L, R - A[p2 - 1]); } else { maxwidth = max(A[p1] - L, R - A[p2 - 1]); maxwidth = max(maxwidth, (int)seg.rangemax(A[p1], A[p2 - 1])); } if (maxwidth < K) { cout << R - L << '\n'; } else { int x = sum[R] - sum[L]; x = (x >= 0 ? x % (2 * K - 1) : ((2 * K - 1) - (-x) % (2 * K - 1)) % (2 * K - 1)); cout << max(x - 1, (2 * K - 1) - x - 1) << '\n'; } } return 0; }