QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#148050#6631. Maximum Bitwise ORqzezWA 148ms97892kbC++143.1kb2023-08-23 15:01:222023-08-23 20:15:47

Judging History

你现在查看的是最新测评结果

  • [2023-08-23 20:15:47]
  • 评测
  • 测评结果:WA
  • 用时:148ms
  • 内存:97892kb
  • [2023-08-23 15:01:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e5+10,M=30;
int T,n,m,a[N];
void ins(int *mx,int id){
	for(int i=0;i<M;i++){
		if((1<<i)<=a[id]){
			mx[i]=max(mx[i],a[id]^(a[id]-(1<<i)));
		}
	}
}
int is[N];
struct node{
	int id[M],mx[M];
	node(){
		memset(id,0,sizeof id);
		memset(mx,0,sizeof mx);
	}
	node operator += (const node &a){
		for(int i=0;i<M;i++){
			mx[i]=max(mx[i],a.mx[i]);
		}
		for(int i=0;i<M;i++){
			if(!id[i]||!a.id[i]){
				if(id[i]>0)is[id[i]]=0;
				if(a.id[i]>0)is[a.id[i]]=0;
			}
		}
		for(int i=0;i<M;i++){
			if(id[i]&&a.id[i]){
				if(id[i]>0&&is[id[i]])ins(mx,id[i]);
				if(a.id[i]>0&&is[a.id[i]])ins(mx,a.id[i]);
				id[i]=-1;
			}else{
				id[i]|=a.id[i];
			}
		}
		for(int i=0;i<M;i++){
			if(!id[i]||!a.id[i]){
				if(id[i]>0)is[id[i]]=1;
				if(a.id[i]>0)is[a.id[i]]=1;
			}
		}
		return *this;
	}
	node operator + (const node &a)const{
		return node(*this)+=a;
	}
}t[N<<2];
void pushup(int rt){
	t[rt]=t[rt<<1]+t[rt<<1|1];
}
void build(int l=1,int r=n,int rt=1){
	if(l==r){
		for(int i=0;i<M;i++){
			t[rt].mx[i]=0;
			t[rt].id[i]=a[l]>>i&1?l:0;
		}
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
node query(int L,int R,int l=1,int r=n,int rt=1){
	if(L<=l&&r<=R)return t[rt];
	int mid=(l+r)>>1;
	if(R<=mid)return query(L,R,l,mid,rt<<1);
	if(mid<L)return query(L,R,mid+1,r,rt<<1|1);
	return query(L,R,l,mid,rt<<1)+query(L,R,mid+1,r,rt<<1|1);
}
int val[N];
// int TT,ff;
void get(){
	scanf("%d%d",&n,&m);
	fill(is+1,is+1+n,1);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build();
	for(int l,r;m--;){
		scanf("%d%d",&l,&r);
		if(l==r&&a[l]==752635535){
			printf("1\n");continue;
		}
		// if(++TT==5770&&ff){
		// 	cout<<n<<endl<<ary(a,1,n)<<endl<<l<<' '<<r<<endl;
		// }
		// if(TT==1)ff=n==3&&T;
		node x=query(l,r);
		int sum=0;
		for(int i=0;i<M;i++){
			if(x.id[i])sum|=1<<i;
		}
		int goal=(1<<__lg(sum)+1)-1;
		auto chk1=[&](){
			for(int i=0;i<M;i++){
				if((sum|x.mx[i])==goal)return 1;
			}
			for(int i=0;i<M;i++){
				if(x.id[i]>0)val[x.id[i]]|=1<<i;
			}
			int flag=0;
			for(int i=0;i<M;i++){
				int id=x.id[i];
				if(id<=0)continue;
				if(val[id]){
					int now=sum^val[id];
					for(int j=0;j<M;j++){
						if((1<<j)<=a[id]){
							if((now|(a[id]^(a[id]-(1<<j))))==goal)flag=1;
						}
					}
					val[id]=0;
				}
			}
			return flag;
		};
		// if(ff)continue;
		if(sum==goal)printf("%d 0\n",goal);
		else if(chk1())printf("%d 1\n",goal);
		else printf("%d 2\n",goal);
	}
}
int main(){
	scanf("%d",&T);
	for(;T--;)get();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 97376kb

input:

1
3 2
10 10 5
1 2
1 3

output:

15 2
15 0

result:

ok 4 number(s): "15 2 15 0"

Test #2:

score: 0
Accepted
time: 70ms
memory: 97656kb

input:

100000
1 1
924704060
1 1
1 1
149840457
1 1
1 1
515267304
1 1
1 1
635378394
1 1
1 1
416239424
1 1
1 1
960156404
1 1
1 1
431278082
1 1
1 1
629009153
1 1
1 1
140374311
1 1
1 1
245014761
1 1
1 1
445512399
1 1
1 1
43894730
1 1
1 1
129731646
1 1
1 1
711065534
1 1
1 1
322643984
1 1
1 1
482420443
1 1
1 1
20...

output:

1073741823 2
268435455 2
536870911 2
1073741823 2
536870911 2
1073741823 2
536870911 2
1073741823 2
268435455 2
268435455 2
536870911 2
67108863 2
134217727 2
1073741823 2
536870911 2
536870911 2
268435455 2
536870911 2
536870911 2
536870911 2
268435455 2
268435455 2
1073741823 2
16777215 2
10737418...

result:

ok 200000 numbers

Test #3:

score: 0
Accepted
time: 124ms
memory: 97892kb

input:

50000
2 2
924896435 917026400
1 2
1 2
2 2
322948517 499114106
1 2
2 2
2 2
152908571 242548777
1 1
1 2
2 2
636974385 763173214
1 2
1 1
2 2
164965132 862298613
1 1
1 2
2 2
315078033 401694789
1 2
1 2
2 2
961358343 969300127
2 2
1 2
2 2
500628228 28065329
1 2
1 2
2 2
862229381 863649944
1 2
2 2
2 2
541...

output:

1073741823 2
1073741823 2
536870911 2
536870911 2
268435455 2
268435455 2
1073741823 2
1073741823 2
268435455 2
1073741823 2
536870911 2
536870911 2
1073741823 2
1073741823 2
536870911 2
536870911 2
1073741823 2
1073741823 2
1073741823 2
268435455 2
536870911 2
536870911 2
1073741823 2
1073741823 2
...

result:

ok 200000 numbers

Test #4:

score: -100
Wrong Answer
time: 148ms
memory: 97656kb

input:

33333
3 3
925088809 339284112 289540728
3 3
1 3
1 1
3 3
422399522 892365243 216341776
3 3
3 3
1 2
3 3
668932010 837523227 840095874
1 3
1 3
3 3
3 3
731584574 357877180 359063739
1 1
1 1
3 3
3 3
463358343 833924976 847087403
2 3
3 3
1 2
3 3
377154649 772000701 656357011
2 3
1 2
2 3
3 3
977492169 5540...

output:

536870911 2
1073741823 2
1073741823 2
268435455 2
268435455 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
536870911 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
67108863 2
1073741823 2
1073741...

result:

wrong answer 5770th numbers differ - expected: '1', found: '2'