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

提出ソース

結果

問題	No.2592 おでぶなおばけさん 2
ユーザー	tko919
提出日時	2023-12-20 00:30:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	209 ms / 2,500 ms
コード長	14,247 bytes
コンパイル時間	3,323 ms
コンパイル使用メモリ	222,952 KB
実行使用メモリ	20,608 KB
最終ジャッジ日時	2023-12-20 11:15:19
合計ジャッジ時間	21,789 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	74 ms 10,396 KB
testcase_02	AC	58 ms 8,960 KB
testcase_03	AC	20 ms 6,676 KB
testcase_04	AC	14 ms 6,676 KB
testcase_05	AC	180 ms 19,328 KB
testcase_06	AC	65 ms 9,544 KB
testcase_07	AC	67 ms 9,544 KB
testcase_08	AC	94 ms 12,080 KB
testcase_09	AC	29 ms 6,676 KB
testcase_10	AC	12 ms 6,676 KB
testcase_11	AC	94 ms 12,288 KB
testcase_12	AC	18 ms 6,676 KB
testcase_13	AC	123 ms 14,232 KB
testcase_14	AC	127 ms 14,464 KB
testcase_15	AC	85 ms 11,008 KB
testcase_16	AC	125 ms 14,364 KB
testcase_17	AC	153 ms 16,648 KB
testcase_18	AC	82 ms 11,056 KB
testcase_19	AC	55 ms 8,836 KB
testcase_20	AC	82 ms 11,392 KB
testcase_21	AC	48 ms 8,356 KB
testcase_22	AC	137 ms 15,508 KB
testcase_23	AC	160 ms 16,800 KB
testcase_24	AC	105 ms 12,672 KB
testcase_25	AC	43 ms 7,680 KB
testcase_26	AC	45 ms 7,752 KB
testcase_27	AC	201 ms 20,608 KB
testcase_28	AC	202 ms 20,608 KB
testcase_29	AC	202 ms 20,608 KB
testcase_30	AC	197 ms 20,608 KB
testcase_31	AC	193 ms 20,608 KB
testcase_32	AC	192 ms 20,608 KB
testcase_33	AC	193 ms 20,608 KB
testcase_34	AC	191 ms 20,608 KB
testcase_35	AC	200 ms 20,608 KB
testcase_36	AC	193 ms 20,608 KB
testcase_37	AC	205 ms 20,608 KB
testcase_38	AC	205 ms 20,608 KB
testcase_39	AC	203 ms 20,608 KB
testcase_40	AC	196 ms 20,608 KB
testcase_41	AC	190 ms 20,608 KB
testcase_42	AC	203 ms 20,608 KB
testcase_43	AC	198 ms 20,608 KB
testcase_44	AC	197 ms 20,608 KB
testcase_45	AC	194 ms 20,608 KB
testcase_46	AC	197 ms 20,608 KB
testcase_47	AC	201 ms 20,608 KB
testcase_48	AC	194 ms 20,608 KB
testcase_49	AC	186 ms 20,608 KB
testcase_50	AC	191 ms 20,608 KB
testcase_51	AC	193 ms 20,608 KB
testcase_52	AC	202 ms 20,608 KB
testcase_53	AC	205 ms 20,608 KB
testcase_54	AC	203 ms 20,608 KB
testcase_55	AC	209 ms 20,608 KB
testcase_56	AC	201 ms 20,608 KB
testcase_57	AC	178 ms 19,456 KB
testcase_58	AC	201 ms 20,608 KB
testcase_59	AC	197 ms 20,608 KB
testcase_60	AC	202 ms 20,608 KB
testcase_61	AC	192 ms 20,608 KB
testcase_62	AC	203 ms 20,608 KB
testcase_63	AC	201 ms 20,608 KB
testcase_64	AC	191 ms 20,608 KB
testcase_65	AC	188 ms 20,608 KB
testcase_66	AC	189 ms 20,608 KB
testcase_67	AC	191 ms 20,608 KB
testcase_68	AC	200 ms 20,608 KB
testcase_69	AC	204 ms 20,608 KB
testcase_70	AC	201 ms 20,608 KB
testcase_71	AC	191 ms 20,608 KB
testcase_72	AC	205 ms 20,608 KB
testcase_73	AC	206 ms 20,608 KB
testcase_74	AC	2 ms 6,676 KB
testcase_75	AC	198 ms 20,608 KB
testcase_76	AC	195 ms 20,608 KB
testcase_77	AC	207 ms 20,608 KB
testcase_78	AC	207 ms 20,608 KB
testcase_79	AC	196 ms 20,608 KB
testcase_80	AC	204 ms 20,608 KB
testcase_81	AC	204 ms 20,608 KB
testcase_82	AC	208 ms 20,608 KB
testcase_83	AC	204 ms 20,608 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/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 2 "library/Math/fastdiv.hpp"

struct FastDiv{
    using u64=uint64_t;
    using u128=__uint128_t;
    constexpr FastDiv():m(),s(),x(){}
    constexpr FastDiv(int _m)
        :m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){}
    constexpr int get(){return m;}
    constexpr friend u64 operator/(u64 n,const FastDiv& d){
        return (u128(n)*d.x>>d.s)>>64;
    }
    constexpr friend int operator%(u64 n,const FastDiv& d){
        return n-n/d*d.m;
    }
    constexpr pair<u64,int> divmod(u64 n)const{
        u64 q=n/(*this);
        return {q,n-q*m};
    }
    int m,s; u64 x;
};

/**
 * @brief Fast Division
*/
#line 3 "library/Math/dynamic.hpp"

struct Fp{
    using u64=uint64_t;
    int v;
    static int get_mod(){return _getmod();}
    static void set_mod(int _m){bar=FastDiv(_m);}
    Fp inv() const{
        int tmp,a=v,b=get_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+=get_mod();}
        return x;
    }
    Fp():v(0){}
    Fp(ll x){
        v=x%get_mod();
        if(v<0)v+=get_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){
        v+=x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator-=(const Fp& x){
        v+=get_mod()-x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator*=(const Fp& x){
        v=(u64(v)*x.v)%bar;
        return *this;
    }
    Fp& operator/=(const Fp& x){
        (*this)*=x.inv();
        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;}
private:
    static FastDiv bar;
    static int _getmod(){return bar.get();}
};
FastDiv Fp::bar(998244353);

/**
 * @brief Dynamic Modint
 */
#line 2 "library/Math/miller.hpp"

struct m64 {
    using i64 = int64_t;
    using u64 = uint64_t;
    using u128 = __uint128_t;

    static u64 mod;
    static u64 r;
    static u64 n2;

    static u64 get_r() {
        u64 ret = mod;
        rep(_,0,5) ret *= 2 - mod * ret;
        return ret;
    }

    static void set_mod(u64 m) {
        assert(m < (1LL << 62));
        assert((m & 1) == 1);
        mod = m;
        n2 = -u128(m) % m;
        r = get_r();
        assert(r * mod == 1);
    }
    static u64 get_mod() { return mod; }

    u64 a;
    m64() : a(0) {}
    m64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){};

    static u64 reduce(const u128 &b) {
        return (b + u128(u64(b) * u64(-r)) * mod) >> 64;
    }
    u64 get() const {
        u64 ret = reduce(a);
        return ret >= mod ? ret - mod : ret;
    }
    m64 &operator*=(const m64 &b) {
        a = reduce(u128(a) * b.a);
        return *this;
    }
    m64 operator*(const m64 &b) const { return m64(*this) *= b; }
    bool operator==(const m64 &b) const {
        return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
    }
    bool operator!=(const m64 &b) const {
        return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
    }
    m64 pow(u128 n) const {
        m64 ret(1), mul(*this);
        while (n > 0) {
        if (n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
        }
        return ret;
    }
};
typename m64::u64 m64::mod, m64::r, m64::n2;

bool Miller(ll n){
    if(n<2 or (n&1)==0)return (n==2);
    m64::set_mod(n);
    ll d=n-1; while((d&1)==0)d>>=1;
    vector<ll> seeds;
    if(n<(1<<30))seeds={2, 7, 61};
    else seeds={2, 325, 9375, 28178, 450775, 9780504};
    for(auto& x:seeds){
        if(n<=x)break;
        ll t=d;
        m64 y=m64(x).pow(t);
        while(t!=n-1 and y!=1 and y!=n-1){
            y*=y;
            t<<=1;
        }
        if(y!=n-1 and (t&1)==0)return 0;
    } return 1;
}

/**
 * @brief Miller-Rabin
 */
#line 2 "library/Utility/random.hpp"

namespace Random{
    mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count());
    using u64=unsigned long long;
    u64 get(){
        return randgen();
    }
    template<typename T>T get(T L){
        return get()%(L+1);
    }
    template<typename T>T get(T L,T R){
        return get(R-L)+L;
    }
    double uniform(){
        return double(get(1000000000))/1000000000;
    }
    string str(int n){
        string ret;
        rep(i,0,n)ret+=get('a','z');
        return ret;
    }
    template<typename Iter>void shuffle(Iter first,Iter last){
        if(first==last)return;
        int len=1;
        for(auto it=first+1;it!=last;it++){
            len++;
            int j=get(0,len-1);
            if(j!=len-1)iter_swap(it,first+j);
        }
    }
    template<typename T>vector<T> select(int n,T L,T R){
        set<T> ret;
        while(ret.size()<n)ret.insert(get(L,R));
        return {ALL(ret)};
    }
};

/**
 * @brief Random
 */
#line 8 "sol.cpp"

using P = pair<int, Fp>;
Fp pw[101010];
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;
    ll K;
    io.read(n, q, K);
    vector<ll> a(n);
    io.read(a);
    vector<int> L(q), R(q);
    rep(i, 0, q) {
        io.read(L[i], R[i]);
        L[i]--;
    }

    vector<int> ret(q);
    vector<int> ps;
    rep(_, 0, 5) {
        int p = 1;
        while (!Miller(p)) {
            p = Random::get(101010101, 1010101010);
        }
        Fp::set_mod(p);
        pw[0] = 1;
        rep(i, 0, n) pw[i + 1] = pw[i] * K;
        vector<P> buf(n);
        rep(i, 0, n) buf[i] = {1, a[i]};
        DisjointSparseTable<P, f> dst(buf);
        rep(i, 0, q) {
            auto [_, x] = dst.query(L[i], R[i]);
            if (x != 0)
                ret[i] = 1;
        }
    }
    rep(i, 0, q) io.write(ret[i] ? "Yes" : "No");
    return 0;
}

yukicoder

結果

テストケース

ソースコード