結果

問題 No.2592 おでぶなおばけさん 2
ユーザー AngrySadEight
提出日時 2025-02-23 02:57:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,226 bytes
コンパイル時間 2,823 ms
コンパイル使用メモリ 150,948 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2025-02-23 02:58:30
合計ジャッジ時間 26,720 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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;
    ll mod3 = 1107296257;

    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);
    pow_h2[0] = 1;
    for (ll i = 0; i < n; i++) {
        pow_h2[i + 1] = (pow_h2[i] * (k % mod2)) % mod2;
    }
    vector<ll> pow_h3(n + 1);
    pow_h3[0] = 1;
    for (ll i = 0; i < n; i++) {
        pow_h3[i + 1] = (pow_h3[i] * (k % mod3)) % mod3;
    }
    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;
    }
    vector<ll> hsum3(n + 1);
    hsum3[0] = 0;
    for (ll i = 0; i < n; i++) {
        hsum3[i + 1] =
            (hsum3[i] * (k % mod3) + (a[i] % mod3 + mod3) % mod3) % mod3;
    }
    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;
        ll hval3 = (hsum3[r[i]] + mod3 -
                    (hsum3[l[i] - 1] * pow_h3[r[i] - l[i]]) % mod3) %
                   mod3;
        if (hval1 == 0 && hval2 == 0 && hval3 == 0) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
    }
}
0