結果
問題 | No.2901 Logical Sum of Substring |
ユーザー | ripity |
提出日時 | 2024-09-20 22:36:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 898 ms / 3,000 ms |
コード長 | 1,746 bytes |
コンパイル時間 | 2,661 ms |
コンパイル使用メモリ | 216,144 KB |
実行使用メモリ | 156,156 KB |
最終ジャッジ日時 | 2024-09-20 22:36:39 |
合計ジャッジ時間 | 24,065 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 8 ms
6,940 KB |
testcase_03 | AC | 8 ms
6,944 KB |
testcase_04 | AC | 8 ms
6,940 KB |
testcase_05 | AC | 8 ms
6,940 KB |
testcase_06 | AC | 8 ms
6,944 KB |
testcase_07 | AC | 7 ms
6,944 KB |
testcase_08 | AC | 782 ms
156,004 KB |
testcase_09 | AC | 811 ms
156,008 KB |
testcase_10 | AC | 797 ms
156,136 KB |
testcase_11 | AC | 870 ms
156,068 KB |
testcase_12 | AC | 870 ms
156,104 KB |
testcase_13 | AC | 856 ms
156,128 KB |
testcase_14 | AC | 898 ms
156,156 KB |
testcase_15 | AC | 867 ms
155,952 KB |
testcase_16 | AC | 894 ms
156,132 KB |
testcase_17 | AC | 837 ms
156,000 KB |
testcase_18 | AC | 812 ms
155,944 KB |
testcase_19 | AC | 835 ms
156,024 KB |
testcase_20 | AC | 850 ms
155,960 KB |
testcase_21 | AC | 821 ms
156,044 KB |
testcase_22 | AC | 872 ms
156,128 KB |
testcase_23 | AC | 782 ms
155,992 KB |
testcase_24 | AC | 809 ms
156,096 KB |
testcase_25 | AC | 776 ms
156,024 KB |
testcase_26 | AC | 800 ms
155,940 KB |
testcase_27 | AC | 770 ms
155,944 KB |
testcase_28 | AC | 779 ms
155,988 KB |
testcase_29 | AC | 838 ms
156,088 KB |
testcase_30 | AC | 806 ms
156,072 KB |
testcase_31 | AC | 829 ms
156,096 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/segtree> using namespace atcoder; int K; const int INF = 1 << 20; struct S { int len; vector<int> l, r; }; S op(S x, S y) { int len_xy = min(x.len, y.len); for(int i = 0; i < K; i++) { int r = x.r[i]; bool valid = (x.r[i] != -INF); for(int j = 0; j < K; j++) { if(x.r[i] > x.r[j] || x.r[j] == -INF) { r = max(r, y.l[j]); if(y.l[j] == INF) valid = false; }else { r = max(r, x.r[j]); } } // if(valid) cout << "@ " << i << " " << x.l[i] << " " << x.r[i] << " : " << y.l[1] << "\n"; if(valid) len_xy = min(len_xy, r - x.r[i] + 1); } vector<int> l_xy(K), r_xy(K); for(int i = 0; i < K; i++) { l_xy[i] = min(x.l[i], y.l[i]); r_xy[i] = max(x.r[i], y.r[i]); } return S{len_xy, l_xy, r_xy}; } S e() { int len = INF; vector<int> l(K, INF), r(K, -INF); return S{len, l, r}; } S gen_s(int i, int v) { vector<int> l(K, INF), r(K, -INF); for(int j = 0; j < K; j++) { if((v >> j) & 1) { l[j] = r[j] = i; } } return S{(v == (1 << K) - 1) ? 1 : INF, l, r}; } int main() { int N; cin >> N >> K; vector<S> seg_init(N); for(int i = 0; i < N; i++) { int a; cin >> a; seg_init[i] = gen_s(i, a); } int Q; cin >> Q; segtree<S, op, e> seg(seg_init); for(int q = 0; q < Q; q++) { int t; cin >> t; if(t == 1) { int i, v; cin >> i >> v; i--; seg.set(i, gen_s(i, v)); } else { int l, r; cin >> l >> r; const S prd = seg.prod(l - 1, r); // for(int i = 0; i < K; i++) cout << "# " << prd.l[i] << " " << prd.r[i] << "\n"; cout << (prd.len > N ? -1 : prd.len) << "\n"; } } }