結果

問題 No.2170 Left Addition Machine
ユーザー 👑 rin204
提出日時 2022-11-28 21:36:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 664 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 4,914 ms
コンパイル使用メモリ 200,304 KB
最終ジャッジ日時 2025-02-09 01:55:01
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using ll = long long;
const int N = 200200;
mint pow2[N];
struct S{
    ll l;
    ll r;
    int size;
    mint ans;
    int anssize;
};
S op(S l, S r){
    if(l.size == -1) return r;
    else if(r.size == -1) return l;
    S ret;
    ret.l = l.l;
    ret.r = r.r;
    ret.size = l.size + r.size;
    if(r.size != r.anssize || l.r >= r.l){
        ret.ans = r.ans;
        ret.anssize = r.anssize;
    }
    else{
        ret.ans = l.ans + (2 * r.ans - r.l) * pow2[l.anssize - 1];
        ret.anssize = l.anssize + r.size;
    }
    return ret;
}
S e(){
    return S{0, 0, -1, 0, 0};
}
int main(){
    pow2[0] = 1;
    for(int i = 1; i < N; i++) pow2[i] = pow2[i - 1] * 2;
    int n, Q;
    cin >> n >> Q;
    vector<S> A(n);
    ll a;
    for(int i = 0; i < n; i++){
        cin >> a;
        A[i] = S{a, a, 1, a, 1};
    }
    segtree<S, op, e> seg(A);
    int l, r;
    while(Q--){
        cin >> l >> r;
        cout << seg.prod(l - 1, r).ans.val() << endl;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0