#939288 (C++17) No.2592 おでぶなおばけさん 2

提出ソース

結果

問題	No.2592 おでぶなおばけさん 2
ユーザー	tko919
提出日時	2023-12-20 00:23:28
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,494 bytes
コンパイル時間	2,848 ms
コンパイル使用メモリ	218,660 KB
実行使用メモリ	18,688 KB
最終ジャッジ日時	2024-09-27 09:12:54
合計ジャッジ時間	11,094 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	14 ms 9,620 KB
testcase_02	AC	15 ms 7,808 KB
testcase_03	AC	6 ms 6,940 KB
testcase_04	AC	5 ms 6,940 KB
testcase_05	AC	33 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	31 ms 12,288 KB
testcase_14	AC	33 ms 12,416 KB
testcase_15	AC	26 ms 9,132 KB
testcase_16	AC	33 ms 12,416 KB
testcase_17	AC	40 ms 14,720 KB
testcase_18	AC	26 ms 9,216 KB
testcase_19	AC	18 ms 7,040 KB
testcase_20	AC	24 ms 9,480 KB
testcase_21	AC	15 ms 6,944 KB
testcase_22	AC	33 ms 13,552 KB
testcase_23	AC	40 ms 14,848 KB
testcase_24	AC	28 ms 10,752 KB
testcase_25	AC	17 ms 6,944 KB
testcase_26	AC	17 ms 6,944 KB
testcase_27	AC	49 ms 18,560 KB
testcase_28	AC	51 ms 18,560 KB
testcase_29	AC	50 ms 18,432 KB
testcase_30	AC	50 ms 18,688 KB
testcase_31	AC	47 ms 18,560 KB
testcase_32	AC	48 ms 18,432 KB
testcase_33	AC	51 ms 18,560 KB
testcase_34	AC	50 ms 18,432 KB
testcase_35	AC	50 ms 18,560 KB
testcase_36	AC	50 ms 18,560 KB
testcase_37	AC	47 ms 18,560 KB
testcase_38	AC	48 ms 18,432 KB
testcase_39	AC	48 ms 18,560 KB
testcase_40	AC	49 ms 18,560 KB
testcase_41	AC	49 ms 18,432 KB
testcase_42	AC	49 ms 18,432 KB
testcase_43	AC	47 ms 18,560 KB
testcase_44	AC	47 ms 18,560 KB
testcase_45	AC	47 ms 18,560 KB
testcase_46	AC	48 ms 18,432 KB
testcase_47	AC	42 ms 18,560 KB
testcase_48	AC	46 ms 18,560 KB
testcase_49	AC	42 ms 18,560 KB
testcase_50	AC	43 ms 18,560 KB
testcase_51	AC	43 ms 18,560 KB
testcase_52	AC	48 ms 18,560 KB
testcase_53	AC	49 ms 18,560 KB
testcase_54	AC	48 ms 18,432 KB
testcase_55	AC	49 ms 18,560 KB
testcase_56	AC	49 ms 18,560 KB
testcase_57	AC	26 ms 18,560 KB
testcase_58	AC	47 ms 18,560 KB
testcase_59	AC	48 ms 18,432 KB
testcase_60	AC	47 ms 18,560 KB
testcase_61	AC	46 ms 18,560 KB
testcase_62	AC	46 ms 18,560 KB
testcase_63	AC	48 ms 18,560 KB
testcase_64	AC	51 ms 18,560 KB
testcase_65	AC	46 ms 18,560 KB
testcase_66	AC	45 ms 18,560 KB
testcase_67	AC	46 ms 18,560 KB
testcase_68	AC	46 ms 18,560 KB
testcase_69	AC	47 ms 18,560 KB
testcase_70	AC	47 ms 18,560 KB
testcase_71	AC	47 ms 18,560 KB
testcase_72	AC	45 ms 18,432 KB
testcase_73	AC	46 ms 18,560 KB
testcase_74	WA	-
testcase_75	AC	46 ms 18,560 KB
testcase_76	AC	49 ms 18,560 KB
testcase_77	AC	48 ms 18,560 KB
testcase_78	AC	48 ms 18,432 KB
testcase_79	AC	49 ms 18,560 KB
testcase_80	AC	48 ms 18,560 KB
testcase_81	AC	47 ms 18,432 KB
testcase_82	AC	47 ms 18,560 KB
testcase_83	AC	49 ms 18,560 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード