Submission #36126910

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64; // 2^64 要用完
#define rep(i,a,n) for(u64 i=a;i<(u64)n;i++)
u64 read(){u64 r;scanf("%llu",&r);return r;}
const int N_MAX=1e6+10;
const int SP=1<<3;
const int SN=1<<SP;//预计算 cache大小
u64 A[N_MAX];
u64 pw[N_MAX]={1};//pw[i]=basis**i,pw[0]=1
u64 hs[N_MAX];//hw[i]=前i个的在nimber下的hash,不需要mod[0,2^{2^k})中的nimber做加乘结果还在[0,2^{2^k})中
u64 small[SN][SN];//预计算
template<bool is_pre=false> // 预计算
u64 nim_product(u64 a,u64 b,int p=1<<6){ // a < (1<<p), b < (1<<p), p=1<<k
  if(min(a,b)<=1)return a*b;
  if(!is_pre and p<=SP)return small[a][b];
  p>>=1;//2^k/2=2^{k-1}
  u64 a0=(a>>p),a1=a&((1ull<<p)-1); // a=a0*2^{2^{k-1}}+a1;
  u64 b0=(b>>p),b1=b&((1ull<<p)-1); // b=b0*2^{2^{k-1}}+b1;
  u64 a1b1=nim_product<is_pre>(a1,b1,p);
  // = ((a0\otimes b0)\otimes 2^{2^{k-1}-1})
  return nim_product<is_pre>(nim_product<is_pre>(a0,b0,p),1ull<<(p-1),p)^
    // \oplus (2^{2^{k-1}}\cdot ((a0\oplus a1)\otimes(b0\oplus b1)\ominus (a1\oplus b1))\ )
    ((nim_product<is_pre>(a0^a1,b0^b1,p)^a1b1)<<p)^
    // \oplus (a1\otimes b1)
    a1b1;
}
u64 get(int l,int r){return nim_product(hs[l],pw[r-l])^hs[r];} // hs[r]-hs[l]*(basis**(r-l))
int main(){
  int N=read();
  int Q=read();
  rep(i,0,N)A[i]=read();
  rep(i,0,SN)rep(j,0,SN)small[i][j]=nim_product<true>(i,j,SP);
  mt19937_64 rng(time(NULL));//runtime random
  u64 basis=rng();
  rep(i,1,N+1){
    pw[i]=nim_product(pw[i-1],basis);//pw[i]=pw[i-1]*b
    hs[i]=nim_product(hs[i-1],basis)^A[i-1];//hs[i]=hs[i-1]*b+a[i-1]
  }

  while(Q--){//(l,r]
    int l0=read()-1;
    int r0=read();
    int l1=read()-1;
    int r1=read();//l1-l0==r1-r0
    int l2=read()-1;
    int r2=read();
    int l=0;
    int r=min(r2-l2,r0-l0)+1;
    while(l+1<r){//二分找不等的点
      int m=(l+r)/2;
      ((get(l0,l0+m)^get(l1,l1+m)^get(l2,l2+m))?r:l)=m;
    }
    printf("%s\n",(l2+l!=r2 and(l0+l==r0 or (A[l0+l]^A[l1+l])<A[l2+l]))?"Yes":"No");
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:45:9: warning: unused variable ‘r1’ [-Wunused-variable]
   45 |     int r1=read();//l1-l0==r1-r0
      |         ^~
./Main.cpp: In function ‘u64 read()’:
./Main.cpp:5:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | u64 read(){u64 r;scanf("%llu",&r);return r;}
      |                  ~~~~~^~~~~~~~~~~

Judge Result