QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227778 | #6631. Maximum Bitwise OR | ugly2333 | WA | 68ms | 6004kb | C++20 | 1.0kb | 2023-10-27 23:02:40 | 2023-10-27 23:02:40 |
Judging History
answer
//Δ_A
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111111;
int n,q,a[N],f[N][22];
vector<pair<int,int> > v;
int main(){
int T,i,j,x,y,s,o;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
scanf("%d",a+i);
v.clear();
for(i=1;i<=n;i++)
for(x=1;x<=a[i];x<<=1)
v.push_back(make_pair(a[i]-x,i));
sort(v.begin(),v.end());
for(i=1;i<=n;i++)
f[i][0]=a[i];
for(j=1;j<=20;j++)
for(i=1;i<=n;i++)
if(i+(1<<(j-1))<=n)
f[i][j]=f[i][j-1]|f[i+(1<<(j-1))][j-1];
while(q--){
scanf("%d%d",&x,&y);
s=0;
for(j=20,i=x;i<=y;j--)
if(i+(1<<j)<=y+1)
s|=f[i][j],i+=1<<j;
if(s==0)
printf("0 0\n");
else{
o=(1<<(32-__builtin_clz(s)))-1;
printf("%d ",o);
s^=o;
if(!s)
o=0;
else{
i=lower_bound(v.begin(),v.end(),make_pair(s,x))-v.begin();
if(i<v.size()&&v[i].first==s&&v[i].second<=y)
o=1;
else
o=2;
}
printf("%d\n",o);
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5864kb
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: 49ms
memory: 6004kb
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: 60ms
memory: 3804kb
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: 68ms
memory: 5928kb
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'