結果
問題 | No.2901 Logical Sum of Substring |
ユーザー |
![]() |
提出日時 | 2024-09-20 22:36:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 881 ms / 3,000 ms |
コード長 | 1,746 bytes |
コンパイル時間 | 5,268 ms |
コンパイル使用メモリ | 209,852 KB |
最終ジャッジ日時 | 2025-02-24 10:27:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#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"; } } }