提出 #61230752

---

ソースコード 拡げる

// Go in my style.
// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

clock_t sttime;
#define STCLOCK sttime = clock ();
#define TIMENOW fprintf (stderr, "\nNOW TIME COSSEMED: %0.4lf\n", 1.0 * (clock () - sttime) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
}

inline int lowbit (int x){ return x & - x; }
#define log2_(x) (31 ^ __builtin_clz (x))

const int N = 6e5;
int n, m, a[N + 5], lb[N + 5], rb[N + 5];
vector < int > mem[N + 5], fac[N + 5], dv[N + 5];

signed main (){
    STCLOCK

    io::read (n), io::read (m);
    for (int i = 1;i <= n;++ i)
        io::read (a[i]), mem[a[i] / lowbit (a[i])].push_back (log2_ (lowbit (a[i])));
    for (int i = 1;i <= (m << 1);i += 2){
        if (mem[i].empty ()){
            for (int i = 1;i <= n;++ i) puts ("No");
            return 0;
        }
        sort (mem[i].begin (), mem[i].end ());
        mem[i].erase (unique (mem[i].begin (), mem[i].end ()), mem[i].end ());
        for (int j = 3;i * j <= (m << 1);j += 2)
            fac[i * j].push_back (i), dv[i].push_back (i * j);
    }
    for (int i = 1;i <= (m << 1);i += 2){
        rb[i] = mem[i].back ();
        for (int x : fac[i]) rb[i] = min (rb[i], rb[x] - 1);
        if (rb[i] < mem[i][0]) rb[i] = - 1;
        else rb[i] = *(-- upper_bound (mem[i].begin (), mem[i].end (), rb[i]));
        if (rb[i] < 0){
            for (int i = 1;i <= n;++ i) puts ("No");
            return 0;
        }
    }
    for (int i = (m << 1) - 1;i >= 1;i -= 2){
        lb[i] = mem[i][0];
        for (int x : dv[i]) lb[i] = max (lb[i], lb[x] + 1);
        if (lb[i] > mem[i].back ()) lb[i] = 31;
        else lb[i] = *lower_bound (mem[i].begin (), mem[i].end (), lb[i]);
    }
    for (int i = 1, x, y;i <= n;++ i){
        x = a[i] / lowbit (a[i]), y = log2_ (lowbit (a[i]));
        if (lb[x] <= y && y <= rb[x]) puts ("Yes");
        else puts ("No");
    }

    TIMENOW
    return 0;
}

提出情報

ジャッジ結果