結果

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// TLE（を期待する解法）

// 基本的な解法
//   各クエリについて、はじめの合計を B = 0 として
//   a_i = a_l, a_{l + 1}, ..., a_{r-1} に対して以下を順に行う。
//   1. a_i を B に加える。 ← この時点で B % k != 0 のとき、式の形から S != 0 が確定する。すぐに Yes を出力する。
//   2. B を k で割る。
//   最終的に B + a_r != 0 かどうかで判定できる。

// 自明テストケース対策
//   a_l = ... = a_r = 0 が嫌なケースなので、全部 0 だったら No を返す。

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

    vector<ll> a(n);
    for (auto& x : a) {
        cin >> x;
    }

    vector<ll> zero_accumulated(n, 0);
    zero_accumulated[0] = (a[0] == 0 ? 1 : 0);
    for (int i = 1; i < n; i++) {
        zero_accumulated[i] = zero_accumulated[i - 1] + (a[i] == 0 ? 1 : 0);
    }

    for (int _ = 0; _ < q; _++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;

        // 全部 0 のときはすぐに No
        const int zero_num = zero_accumulated[r] - (l > 0 ? zero_accumulated[l - 1] : 0);
        if (zero_num == r - l + 1) {
            cout << "No" << endl;
            continue;
        }

        // 全部 0 ではないとき
        bool Yes = false;
        ll B = 0;

        for (int i = l; i < r; i++) {
            B += a[i];
            if (B % k != 0) {
                Yes = true;
                break;
            }
            B /= k;
        }
        Yes |= (B + a[r] != 0);

        cout << (Yes ? "Yes" : "No") << endl;
    }
}
0