結果

問題 No.2592 おでぶなおばけさん 2
ユーザー tko919tko919
提出日時 2023-12-20 00:23:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 11,494 bytes
コンパイル時間 3,720 ms
コンパイル使用メモリ 218,740 KB
実行使用メモリ 18,560 KB
最終ジャッジ日時 2023-12-20 01:13:11
合計ジャッジ時間 11,985 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 12 ms
9,744 KB
testcase_02 AC 13 ms
7,816 KB
testcase_03 AC 5 ms
6,676 KB
testcase_04 AC 5 ms
6,676 KB
testcase_05 AC 30 ms
18,048 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 30 ms
12,288 KB
testcase_14 AC 30 ms
12,416 KB
testcase_15 AC 23 ms
9,256 KB
testcase_16 AC 31 ms
12,416 KB
testcase_17 AC 36 ms
14,784 KB
testcase_18 AC 24 ms
9,324 KB
testcase_19 AC 17 ms
7,092 KB
testcase_20 AC 21 ms
9,604 KB
testcase_21 AC 14 ms
6,676 KB
testcase_22 AC 29 ms
13,676 KB
testcase_23 AC 36 ms
14,932 KB
testcase_24 AC 26 ms
10,796 KB
testcase_25 AC 14 ms
6,676 KB
testcase_26 AC 15 ms
6,676 KB
testcase_27 AC 43 ms
18,560 KB
testcase_28 AC 43 ms
18,560 KB
testcase_29 AC 43 ms
18,560 KB
testcase_30 AC 42 ms
18,560 KB
testcase_31 AC 44 ms
18,560 KB
testcase_32 AC 45 ms
18,560 KB
testcase_33 AC 45 ms
18,560 KB
testcase_34 AC 46 ms
18,560 KB
testcase_35 AC 44 ms
18,560 KB
testcase_36 AC 45 ms
18,560 KB
testcase_37 AC 45 ms
18,560 KB
testcase_38 AC 44 ms
18,560 KB
testcase_39 AC 44 ms
18,560 KB
testcase_40 AC 45 ms
18,560 KB
testcase_41 AC 46 ms
18,560 KB
testcase_42 AC 45 ms
18,560 KB
testcase_43 AC 47 ms
18,560 KB
testcase_44 AC 45 ms
18,560 KB
testcase_45 AC 45 ms
18,560 KB
testcase_46 AC 45 ms
18,560 KB
testcase_47 AC 40 ms
18,560 KB
testcase_48 AC 42 ms
18,560 KB
testcase_49 AC 41 ms
18,560 KB
testcase_50 AC 40 ms
18,560 KB
testcase_51 AC 40 ms
18,560 KB
testcase_52 AC 45 ms
18,560 KB
testcase_53 AC 44 ms
18,560 KB
testcase_54 AC 44 ms
18,560 KB
testcase_55 AC 45 ms
18,560 KB
testcase_56 AC 44 ms
18,560 KB
testcase_57 AC 26 ms
18,560 KB
testcase_58 AC 44 ms
18,560 KB
testcase_59 AC 43 ms
18,560 KB
testcase_60 AC 42 ms
18,560 KB
testcase_61 AC 43 ms
18,560 KB
testcase_62 AC 42 ms
18,560 KB
testcase_63 AC 42 ms
18,560 KB
testcase_64 AC 43 ms
18,560 KB
testcase_65 AC 42 ms
18,560 KB
testcase_66 AC 41 ms
18,560 KB
testcase_67 AC 40 ms
18,560 KB
testcase_68 AC 41 ms
18,560 KB
testcase_69 AC 42 ms
18,560 KB
testcase_70 AC 42 ms
18,560 KB
testcase_71 AC 42 ms
18,560 KB
testcase_72 AC 41 ms
18,560 KB
testcase_73 AC 41 ms
18,560 KB
testcase_74 AC 44 ms
18,560 KB
testcase_75 AC 44 ms
18,560 KB
testcase_76 AC 50 ms
18,560 KB
testcase_77 AC 46 ms
18,560 KB
testcase_78 AC 46 ms
18,560 KB
testcase_79 AC 44 ms
18,560 KB
testcase_80 AC 45 ms
18,560 KB
testcase_81 AC 44 ms
18,560 KB
testcase_82 AC 43 ms
18,560 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())

using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__int128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__uint128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__int128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__uint128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(double x){
        ostringstream oss;
        oss << fixed << setprecision(15) << double(x);
        string s = oss.str();
        _write(s);
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        _write(head);
        write<ln,true>(tail...); 
        if(space)_write(' ');
    }
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

#line 2 "library/Math/modint.hpp"

template <int mod = 1000000007> struct fp {
    int v;
    static constexpr int get_mod() { return mod; }
    int inv() const {
        int tmp, a = v, b = mod, x = 1, y = 0;
        while (b)
            tmp = a / b, a -= tmp * b, swap(a, b), x -= tmp * y, swap(x, y);
        if (x < 0) {
            x += mod;
        }
        return x;
    }
    fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
    fp operator-() const { return fp() - *this; }
    fp pow(ll t) {
        assert(t >= 0);
        fp res = 1, b = *this;
        while (t) {
            if (t & 1)
                res *= b;
            b *= b;
            t >>= 1;
        }
        return res;
    }
    fp &operator+=(const fp &x) {
        if ((v += x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator-=(const fp &x) {
        if ((v += mod - x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator*=(const fp &x) {
        v = ll(v) * x.v % mod;
        return *this;
    }
    fp &operator/=(const fp &x) {
        v = ll(v) * x.inv() % mod;
        return *this;
    }
    fp operator+(const fp &x) const { return fp(*this) += x; }
    fp operator-(const fp &x) const { return fp(*this) -= x; }
    fp operator*(const fp &x) const { return fp(*this) *= x; }
    fp operator/(const fp &x) const { return fp(*this) /= x; }
    bool operator==(const fp &x) const { return v == x.v; }
    bool operator!=(const fp &x) const { return v != x.v; }
    friend istream &operator>>(istream &is, fp &x) { return is >> x.v; }
    friend ostream &operator<<(ostream &os, const fp &x) { return os << x.v; }
};

template <typename T> T Inv(ll n) {
    static const int md = T::get_mod();
    static vector<T> buf({0, 1});
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static const int md = T::get_mod();
    static vector<T> buf({1, 1}), ibuf({1, 1});
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r, inv);
}

/**
 * @brief Modint
 */
#line 5 "sol.cpp"
using Fp = fp<998244353>;
#line 2 "library/DataStructure/disjointsparsetable.hpp"

template<typename T,T (*f)(T,T)>struct DisjointSparseTable{
    vector<vector<T>> buf;
    vector<int> height;
    DisjointSparseTable(const vector<T>& a){
        int n=a.size(),LG=0;
        while((1<<LG)<=n)LG++;
        buf.assign(LG,vector<T>(n));
        height.assign(1<<LG,0);
        rep(i,2,1<<LG)height[i]=height[i>>1]+1;
        rep(i,0,n)buf[0][i]=a[i];
        rep(lg,1,LG){
            int add=1<<lg;
            for(int j=0;j<n;j+=(add<<1)){
                int pos=min(j+add,n);
                buf[lg][pos-1]=a[pos-1];
                for(int k=pos-2;k>=j;k--)buf[lg][k]=f(a[k],buf[lg][k+1]);
                if(n<=pos)break;
                buf[lg][pos]=a[pos];
                for(int k=pos+1;k<min(pos+add,n);k++)buf[lg][k]=f(buf[lg][k-1],a[k]);
            }
        }
    }
    T query(int L,int R){
        if(L>=--R)return buf[0][L];
        return f(buf[height[L^R]][L],buf[height[L^R]][R]);
    }
};

/**
 * @brief Disjoint Sparse Table
 */
#line 7 "sol.cpp"

using P = pair<int, Fp>;
vector<Fp> pw;
P f(P a, P b) {
    a.second += b.second * pw[a.first];
    a.first += b.first;
    return a;
}

FastIO io;
int main() {
    int n, q, K;
    io.read(n, q, K);
    pw.resize(n + 1, 1);
    rep(i, 0, n) pw[i + 1] = pw[i] * K;
    vector<P> buf(n);
    rep(i, 0, n) {
        int x;
        io.read(x);
        buf[i] = {1, x};
    }
    DisjointSparseTable<P, f> dst(buf);
    while (q--) {
        int L, R;
        io.read(L, R);
        L--;
        auto [_, x] = dst.query(L, R);
        io.write(x == 0 ? "No" : "Yes");
    }
    return 0;
}
0