提出 #35934684

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using mat=array<ull,64>;
#define rep(i,l,r)for(int i=(l);i<(r);i++)
#define bit(s,i)(((s)>>(i))&1)

mt19937_64 rand_gen;

mat mat_gen(){
	mat ret;
	rep(i,0,64)ret[i]=rand_gen();
	return ret;
}

ull mat_prod(mat&m,ull x){
	ull ans=0;
	rep(i,0,64)if(bit(x,i))ans^=m[i];
	return ans;
}

mat mat_mul(mat&x,mat&y){
	mat ret;
	rep(i,0,64)ret[i]=mat_prod(y,x[i]);
	return ret;
}

int main(){
	vector<mat>m(20);
	m[0]=mat_gen();
	rep(i,1,20)m[i]=mat_mul(m[i-1],m[i-1]);
	
	int n,q;
	cin >> n >> q;
	vector<vector<ull>>hash(20,vector<ull>(n));
	rep(i,0,n)cin >> hash[0][i];
	
	rep(i,1,20)rep(j,0,n-(1<<i)+1){
		hash[i][j] = hash[i-1][j] ^ mat_prod(m[i-1],hash[i-1][j+(1<<(i-1))]);
	}
	
	rep(_,0,q){
		int A,B,C,D,E,F;
		cin >> A >> B >> C >> D >> E >> F;
		A--,B--,C--,D--,E--,F--;
		int x=A,y=C,z=E;
		for(int i=19;i>=0;i--){
			if(max({x,y,z})+(1<<i)>n)continue;
			if((hash[i][x]^hash[i][y])!=hash[i][z])continue;
			x+=1<<i;
			y+=1<<i;
			z+=1<<i;
		}
		if(x>B||y>D||z>F)cout << (F-E>B-A?"Yes":"No") << endl;
		else cout << ((hash[0][x]^hash[0][y])<hash[0][z]?"Yes":"No") << endl;
	}
}

提出情報

ジャッジ結果