QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#375567#6631. Maximum Bitwise ORwsc2008WA 297ms212728kbC++142.5kb2024-04-03 13:06:022024-04-03 13:06:03

Judging History

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

  • [2024-04-03 13:06:03]
  • 评测
  • 测评结果:WA
  • 用时:297ms
  • 内存:212728kb
  • [2024-04-03 13:06:02]
  • 提交

answer

#include<bits/stdc++.h>
typedef int ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=1e5+9;
ll T,n,q,a[N],sum[31][N],pos[31][N],cnt[31];
ll f[466][N],bin[31][31],id[31][31],tid;
bool debug=1;
ll cq;
vector<ll>spe[N];
void solve(ll tid){
	n=read(),q=read();
	if(tid==1)debug&=(n==3&&q==3);
	rep(i,1,n)a[i]=read();
	if(debug&&tid==1553){
		rep(i,1,n)cout<<a[i]<<" ";
		cout<<endl;
	}
	rep(i,0,30){
		rep(j,0,n)sum[i][j]=pos[i][j]=0;
	}
	rep(i,0,465){
		rep(j,0,n)f[i][j]=0;
	}
	rep(i,0,30){
		rep(j,1,n){
			sum[i][j]=sum[i][j-1]+((a[j]>>i)&1);
			pos[i][j]=pos[i][j-1]+((a[j]>>i)&1)*j;
		}
	}
	rep(i,1,n){
		memset(bin,0,sizeof(bin));
		ll cur=30;
		per(j,30,0){
			if((a[i]>>j)&1)cur=j;
			if(cur<30){
				rep(k,j,cur)bin[j][k]=1;
			}
		}
		cur=0;
		rep(j,0,30){
			rep(k,j,30)f[cur++][i]=bin[j][k];
		}
	}
	rep(i,0,465){
		rep(j,1,n)f[i][j]+=f[i][j-1];
	}
	while(q--){
		ll l=read(),r=read(),top=30;
		if(debug&&tid==1553)cout<<l<<" "<<r<<endl;
		while(top>=0&&sum[top][r]-sum[top][l-1]==0)top--;
		if(!(~top)){
			if(!debug)puts("0 0");
			continue;
		}
		if(!debug)write((2<<top)-1),putchar(' ');
		rep(i,0,top)cnt[i]=sum[i][r]-sum[i][l-1];
		vector<ll>tar;
		ll L=31,R=-1;
		rep(i,0,top){
			if(cnt[i]==1){
				ll p=pos[i][r]-pos[i][l-1];
				tar.push_back(p);
				spe[p].push_back(i);
			}
			if(!cnt[i])L=min(L,i),R=max(R,i);
		}
		if(L>R){
			if(!debug)puts("0");
			for(ll i:tar)spe[i].clear();
			continue;
		}
		sort(tar.begin(),tar.end());
		tar.resize(unique(tar.begin(),tar.end())-tar.begin());
		ll rid=id[L][R],qq=f[rid][r]-f[rid][l-1];
		for(ll i:tar){
			sort(spe[i].begin(),spe[i].end());
			ll st=f[rid][i]-f[rid][i-1];
			qq-=st;
			ll nid=id[min(spe[i][0],L)][max(spe[i].back(),R)];
			qq+=f[nid][i]-f[nid][i-1];
		}
		if(!debug){
			if(qq)puts("1");
			else puts("2");
		}
		for(ll i:tar)spe[i].clear();
	}
}
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	rep(i,0,30){
		rep(j,i,30)id[i][j]=++tid;
	}
	T=read();
	debug&=(T==33333);
	rep(tid,1,T)solve(tid);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 212728kb

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: 297ms
memory: 212376kb

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: 203ms
memory: 211704kb

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: 175ms
memory: 210944kb

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:

169019744 945504599 369619596 
1 2
2 3
2 3

result:

wrong answer 1st numbers differ - expected: '536870911', found: '169019744'