QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#127254#6631. Maximum Bitwise ORyy_zq#WA 127ms3624kbC++141.4kb2023-07-19 14:50:422023-07-19 14:50:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 14:50:44]
  • 评测
  • 测评结果:WA
  • 用时:127ms
  • 内存:3624kb
  • [2023-07-19 14:50:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;++i) 
#define mid (l+r>>1)
const int MAX = 1e5+111;
int a[MAX];
int seg[MAX*4][32];
int que[32];
void build(int l,int r,int x){
	if(l==r){
		FOR(i,0,30) if((1ll<<i)&a[l]) seg[x][i]=1;else seg[x][i]=0;
		return;
	}
	build(l,mid,x<<1),build(mid+1,r,x<<1|1);
	FOR(i,0,30) seg[x][i]=seg[x<<1][i]+seg[x<<1|1][i];
}
void ask(int l,int r,int x,int lft,int rht){
	if(l>rht||r<lft) return;
	if(l>=lft&&r<=rht){
		FOR(i,0,30) que[i] += seg[x][i];
		return;
	}
	ask(l,mid,x<<1,lft,rht),ask(mid+1,r,x<<1|1,lft,rht);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n,q;
		cin>>n>>q;
		FOR(i,1,n) cin>>a[i];
		build(1,n,1);
		FOR(u,1,q){
			int l,r;
			cin>>l>>r;
			FOR(j,0,30) que[j]=0;
			ask(1,n,1,l,r);
			int tmp[30]={},pos[30]={},head = 1,tail = 0;
			int max_or=0,us=0;
			for(int i=30;i>=0;--i){
				if(que[i]){
					if(que[i]>1){
						pos[++tail] = i;
						tmp[  tail] = que[i]-1;
					}
					max_or|=(1ll<<i);
				}
				else{
					if(tail){
						tmp[tail] --;
						us+=pos[tail]-i;
						while(tail>=1&&tmp[tail]==0){
							--tail;
						}
						max_or|=(1ll<<i);
					}
				}
			}
			cout<<max_or<<' '<<us<<endl;
		}
	}
	return 0;
}
/*
2
3 2
10 10 5
1 2
1 3
3 2
10 10 5
1 2
1 3
*/

详细

Test #1:

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

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: -100
Wrong Answer
time: 127ms
memory: 3624kb

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:

924704060 0
149840457 0
515267304 0
635378394 0
416239424 0
960156404 0
431278082 0
629009153 0
140374311 0
245014761 0
445512399 0
43894730 0
129731646 0
711065534 0
322643984 0
482420443 0
202661591 0
529979773 0
520572847 0
500838890 0
224446016 0
228171383 0
973333717 0
8493236 0
622547486 0
677...

result:

wrong answer 1st numbers differ - expected: '1073741823', found: '924704060'