結果
問題 | No.1654 Binary Compression |
ユーザー | ygussany |
提出日時 | 2021-06-17 22:31:57 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 335 ms / 2,000 ms |
コード長 | 2,411 bytes |
コンパイル時間 | 281 ms |
コンパイル使用メモリ | 33,280 KB |
実行使用メモリ | 201,344 KB |
最終ジャッジ日時 | 2024-10-14 02:13:26 |
合計ジャッジ時間 | 5,884 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 70 ms
10,112 KB |
testcase_11 | AC | 71 ms
10,368 KB |
testcase_12 | AC | 74 ms
10,496 KB |
testcase_13 | AC | 75 ms
10,496 KB |
testcase_14 | AC | 71 ms
10,368 KB |
testcase_15 | AC | 73 ms
10,368 KB |
testcase_16 | AC | 50 ms
16,384 KB |
testcase_17 | AC | 49 ms
16,384 KB |
testcase_18 | AC | 74 ms
10,624 KB |
testcase_19 | AC | 74 ms
10,496 KB |
testcase_20 | AC | 74 ms
10,624 KB |
testcase_21 | AC | 75 ms
10,496 KB |
testcase_22 | AC | 74 ms
10,496 KB |
testcase_23 | AC | 15 ms
5,248 KB |
testcase_24 | AC | 15 ms
5,248 KB |
testcase_25 | AC | 15 ms
5,248 KB |
testcase_26 | AC | 15 ms
5,248 KB |
testcase_27 | AC | 138 ms
12,672 KB |
testcase_28 | AC | 146 ms
12,672 KB |
testcase_29 | AC | 15 ms
5,248 KB |
testcase_30 | AC | 15 ms
5,248 KB |
testcase_31 | AC | 15 ms
5,248 KB |
testcase_32 | AC | 15 ms
5,248 KB |
testcase_33 | AC | 138 ms
12,672 KB |
testcase_34 | AC | 148 ms
12,672 KB |
testcase_35 | AC | 16 ms
5,248 KB |
testcase_36 | AC | 16 ms
5,248 KB |
testcase_37 | AC | 16 ms
5,504 KB |
testcase_38 | AC | 16 ms
5,248 KB |
testcase_39 | AC | 14 ms
5,248 KB |
testcase_40 | AC | 14 ms
5,248 KB |
testcase_41 | AC | 14 ms
5,248 KB |
testcase_42 | AC | 155 ms
201,216 KB |
testcase_43 | AC | 157 ms
201,216 KB |
testcase_44 | AC | 14 ms
5,248 KB |
testcase_45 | AC | 14 ms
5,248 KB |
testcase_46 | AC | 158 ms
201,344 KB |
testcase_47 | AC | 1 ms
5,248 KB |
testcase_48 | AC | 1 ms
5,248 KB |
testcase_49 | AC | 335 ms
39,808 KB |
testcase_50 | AC | 335 ms
39,920 KB |
testcase_51 | AC | 192 ms
105,984 KB |
testcase_52 | AC | 191 ms
105,984 KB |
ソースコード
#include <stdio.h> #include <stdlib.h> const int Mod = 924844033; typedef struct { int left, right; long long sum, lx; } lazy_seg_node; void init_node(lazy_seg_node v[], int k, int l, int r) { v[k].left = l; v[k].right = r; v[k].sum = 0; v[k].lx = -1; if (l < r) { init_node(v, k << 1, l, (l + r) / 2); init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r); } } void update_segment(lazy_seg_node v[], int k, int l, int r, long long x) { int i, j; if (v[k].left > r || v[k].right < l) return; else if (v[k].left >= l && v[k].right <= r) { v[k].lx = x; v[k].sum = (x * (v[k].right - v[k].left + 1)) % Mod; for (j = k, i = j >> 1; i > 0; j = i, i >>= 1) v[i].sum = (v[j].sum + v[j^1].sum) % Mod; } else { if (v[k].lx >= 0) { j = k << 1; v[j].sum = (v[k].lx * (v[j].right - v[j].left + 1)) % Mod; v[j^1].sum = (v[k].lx * (v[j^1].right - v[j^1].left + 1)) % Mod; v[j].lx = v[k].lx; v[j^1].lx = v[k].lx; v[k].lx = -1; } update_segment(v, k << 1, l, r, x); update_segment(v, (k << 1) ^ 1, l, r, x); } } long long get_sum(lazy_seg_node v[], int k, int l, int r) { int j; if (v[k].left > r || v[k].right < l) return 0; else if (v[k].left >= l && v[k].right <= r) return v[k].sum; else { if (v[k].lx >= 0) { j = k << 1; v[j].sum = (v[k].lx * (v[j].right - v[j].left + 1)) % Mod; v[j^1].sum = (v[k].lx * (v[j^1].right - v[j^1].left + 1)) % Mod; v[j].lx = v[k].lx; v[j^1].lx = v[k].lx; v[k].lx = -1; } return (get_sum(v, k << 1, l, r) + get_sum(v, (k << 1) ^ 1, l, r)) % Mod; } } int main() { char S[3000001]; scanf("%s", S); int i, j, k = 0, n = 0, A[3000001]; lazy_seg_node *v; for (i = 0; S[i] != 0; i = j) { if (S[i] != '0' && S[i] != '1') return -1; for (j = i + 1; S[j] == S[i]; j++); if (S[i] == '0') { if (n < j - i) n = j - i; A[k++] = i - j; } else A[k++] = j - i; } if (i > 3000000) return -1; v = (lazy_seg_node*)malloc(sizeof(lazy_seg_node) * (n + 1) * 4); init_node(v, 1, 1, n); long long ans = 1, zero_lr = 1; if (A[k-1] < 0) zero_lr = -A[--k] + 1; if (k > 0) { if (A[0] < 0) zero_lr = zero_lr * (-A[0] + 1) % Mod; ans = A[k-1]; for (i = k - 3, j = k - 2; i >= 0; i -= 2, j -= 2) { update_segment(v, 1, 1, -A[j], ans); ans += (get_sum(v, 1, 1, n) + 1) * A[i] % Mod; if (ans >= Mod) ans -= Mod; } } else zero_lr--; printf("%lld\n", ans * zero_lr % Mod); fflush(stdout); return 0; }