結果

問題 No.2592 おでぶなおばけさん 2
ユーザー AngrySadEight
提出日時 2025-02-23 02:45:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,703 bytes
コンパイル時間 3,456 ms
コンパイル使用メモリ 151,184 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2025-02-23 02:46:28
合計ジャッジ時間 32,440 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 78 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <atcoder/all>
#include <iostream>
#include <vector>
using namespace std;
using namespace atcoder;
using ll = long long;
using pll = pair<ll, ll>;

int main() {
    ll n, q, k;
    cin >> n >> q >> k;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    reverse(a.begin(), a.end());
    vector<ll> l(q);
    vector<ll> r(q);
    for (ll i = 0; i < q; i++) {
        cin >> l[i] >> r[i];

        ll rev_l = n - r[i] + 1;
        ll rev_r = n - l[i] + 1;
        l[i] = rev_l;
        r[i] = rev_r;
    }
    ll mod1 = 998244853;
    ll mod2 = 1000000009;

    vector<ll> pow_h1(n + 1);
    pow_h1[0] = 1;
    for (ll i = 0; i < n; i++) {
        pow_h1[i + 1] = (pow_h1[i] * (k % mod1)) % mod1;
    }
    vector<ll> pow_h2(n + 1);
    for (ll i = 0; i < n; i++) {
        pow_h2[i + 1] = (pow_h2[i] * (k % mod2)) % mod2;
    }
    vector<ll> hsum1(n + 1);
    hsum1[0] = 0;
    for (ll i = 0; i < n; i++) {
        hsum1[i + 1] =
            (hsum1[i] * (k % mod1) + (a[i] % mod1 + mod1) % mod1) % mod1;
    }
    vector<ll> hsum2(n + 1);
    hsum2[0] = 0;
    for (ll i = 0; i < n; i++) {
        hsum2[i + 1] =
            (hsum2[i] * (k % mod2) + (a[i] % mod2 + mod2) % mod2) % mod2;
    }
    for (ll i = 0; i < q; i++) {
        ll hval1 = (hsum1[r[i]] + mod1 -
                    (hsum1[l[i] - 1] * pow_h1[r[i] - l[i]]) % mod1) %
                   mod1;
        ll hval2 = (hsum2[r[i]] + mod2 -
                    (hsum2[l[i] - 1] * pow_h2[r[i] - l[i]]) % mod2) %
                   mod2;
        if (hval1 == 0 && hval2 == 0) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
    }
}
0