QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127254 | #6631. Maximum Bitwise OR | yy_zq# | WA | 127ms | 3624kb | C++14 | 1.4kb | 2023-07-19 14:50:42 | 2023-07-19 14:50:44 |
Judging History
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'