結果

問題 No.2592 おでぶなおばけさん 2
コンテスト
ユーザー nu50218
提出日時 2023-12-10 12:22:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,687 bytes
コンパイル時間 2,357 ms
コンパイル使用メモリ 205,820 KB
最終ジャッジ日時 2025-02-18 09:59:47
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 77 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/segtree.hpp>

using namespace std;
using ll = long long;

// 有名MODたちでチェックする、WAを期待する解法
const ll MOD1 = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = (1LL << 61) - 1;
static_assert(MOD1 < numeric_limits<ll>::max() / 2);
static_assert(MOD2 < numeric_limits<ll>::max() / 2);
static_assert(MOD3 < numeric_limits<ll>::max() / 2);

using S = tuple<ll, ll, ll>;
S op(const S a, const S b) {
    auto [a1, a2, a3] = a;
    auto [b1, b2, b3] = b;
    return {(a1 + b1) % MOD1, (a2 + b2) % MOD2, (a3 + b3) % MOD3};
}
S e() {
    return {0, 0, 0};
}
using segtree = atcoder::segtree<S, op, e>;

int main() {
    ll n, q, k;
    cin >> n >> q >> k;

    vector<S> a;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        a.push_back({
            (x % MOD1 + MOD1) % MOD1,
            (x % MOD2 + MOD2) % MOD2,
            (x % MOD3 + MOD3) % MOD3,
        });
    }

    // b[i] := (a[i] * pow(k, i)) % MOD
    vector<S> b(n);
    __uint128_t powk1 = 1, powk2 = 1, powk3 = 1;
    for (int i = 0; i < n; i++) {
        // a[i], powk ともに MOD < 2^63 以下なので、128ビットで十分
        auto [ai1, ai2, ai3] = a[i];
        b[i] = {
            (ai1 * powk1) % MOD1,
            (ai2 * powk2) % MOD2,
            (ai3 * powk3) % MOD3,
        };

        powk1 = (powk1 * k) % MOD1;
        powk2 = (powk2 * k) % MOD2;
        powk3 = (powk3 * k) % MOD3;
    }

    segtree st(b);

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << (st.prod(l, r + 1) != make_tuple(0, 0, 0) ? "Yes" : "No") << endl;
    }
}
0