結果

問題 No.2901 Logical Sum of Substring
コンテスト
ユーザー lmxyue
提出日時 2025-08-25 14:10:22
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 255 ms / 3,000 ms
+ 19µs
コード長 2,308 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,152 ms
コンパイル使用メモリ 287,560 KB
実行使用メモリ 102,656 KB
最終ジャッジ日時 2026-07-14 11:35:02
合計ジャッジ時間 12,373 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001LL
int N,K;
struct Data{
        vector<pair<int,int>> pre,suf;
        int ans = Inf32;
        int sz = 0;
};

Data op(Data a,Data b){
        Data res;
        res.ans = min(a.ans,b.ans);
        res.sz = a.sz + b.sz;
        rep(i,a.suf.size()){
                rep(j,b.pre.size()){
                        if(((a.suf[i].first | b.pre[j].first)==(1<<K)-1)){
                                res.ans = min(res.ans,a.suf[i].second+b.pre[j].second);
                        }
                }
        }
        res.pre = a.pre;
        rep(i,b.pre.size()){
                int v = b.pre[i].first | a.pre.back().first;
                if(v!=res.pre.back().first){
                        res.pre.push_back({v,a.sz + b.pre[i].second});
                }
        }
        res.suf = b.suf;
        rep(i,a.suf.size()){
                int v = a.suf[i].first | b.suf.back().first;
                if(v!=res.suf.back().first){
                        res.suf.push_back({v,a.suf[i].second + b.sz});
                }
        }
        return res;
}

Data e(){
        Data res;
        res.pre = {{0,0}},res.suf = {{0,0}};
        return res;
}
Data make(int v){
        Data res = e();
        res.sz = 1;
        if(v==0)return res;
        res.pre.push_back({v,1});
        res.suf.push_back({v,1});
        if(v==(1<<K)-1)res.ans = 1;
        return res;
}
int main(){
        
        cin>>N>>K;
        vector<Data> a(N);
        rep(i,N){
                int t;
                cin>>t;
                a[i] = make(t);
        }
        segtree<Data,op,e> seg(a);
        int _q;
        
        cin>>_q;
        rep(_,_q){
                int t,x,y;
                cin>>t>>x>>y;
                if(t==1){
                        seg.set(x-1,make(y));
                }
                else{
                        auto ret = seg.prod(x-1,y);
                        if(ret.ans==Inf32)cout<<-1<<endl;
                        else
                        cout<<ret.ans<<endl;
                }
        }
                        
        
        return 0;
}
0