QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122695 | #6631. Maximum Bitwise OR | installb# | WA | 308ms | 83744kb | C++14 | 2.9kb | 2023-07-10 22:20:58 | 2023-07-10 22:21:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define M 100005
int n,q,A[M];
using pii = pair<int,int>;
pii Ask(int x){
int l=-1,r=-1,i=0;
while(x){
if(x&1);
else {
if(l==-1)l = i;
r=i;
}
i++;
x>>=1;
}
return pii(l,r);
}
int nex[30][M];
struct Seg{
struct TNODE{
int l,r,mx;
}tree[M<<2];
#define fa tree[p]
#define lson tree[p<<1]
#define rson tree[p<<1|1]
void build(int l,int r,int *A,int p=1){
fa.l=l,fa.r=r;
if(l==r)return void(fa.mx = A[l]);
int mid=l+r>>1;
build(l,mid,A,p<<1);
build(mid+1,r,A,p<<1|1);
fa.mx=max(lson.mx,rson.mx);
}
int Query(int l,int r,int p=1){
if(l==fa.l&&r==fa.r)return fa.mx;
int mid=fa.l+fa.r>>1;
if(r<=mid)return Query(l,r,p<<1);
else if(l>mid)return Query(l,r,p<<1|1);
else return max(Query(l,mid,p<<1),Query(mid+1,r,p<<1|1));
}
#undef fa
#undef lson
#undef rson
}T[30];
int cnt[30][M],pre[30][M];
pii solve(int l,int r){
int x=0,mx=-1;
vector<int>pl;
for(int i=0;i<30;i++){
if(cnt[i][r]-cnt[i][l-1]==0)continue;
x|=1<<i;
if(cnt[i][r]-cnt[i][l-1]==1)pl.push_back(pre[i][r]);
mx = i;
}
sort(pl.begin(),pl.end());
unique(pl.begin(),pl.end());
auto [bl,br] = Ask(x);
if(bl==-1) return pii((1<<mx+1)-1,0);
int last = l;
for(int &p_pl:pl){
if(p_pl-1 >= last){
if(T[bl].Query(last,p_pl-1) >= br) return pii((1<<mx+1)-1,1);
}
int res = 0, mx2 = -1;
for(int i=0;i<30;i++)if(cnt[i][r]-cnt[i][p_pl]+cnt[i][p_pl-1]-cnt[i][l-1]>0){
res |= 1<<i;
mx2 = i;
}
auto [bl2,br2] = Ask(res);
if(mx2==mx){
if(nex[bl2][p_pl]>=br2) return pii((1<<mx+1)-1,1);
}else {
if(nex[bl2][p_pl]>=max(br2,mx)) return pii((1<<mx+1)-1,1);
}
last = p_pl+1;
}
if(r >= last){
if(T[bl].Query(last,r) >= br) return pii((1<<mx+1)-1,1);
}
return pii((1<<mx+1)-1,2);
}
int main(){
int Cas;cin>>Cas;
while(Cas--){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&A[i]);
int last = -1;
for(int j=29;~j;--j){
if((1<<j)&A[i])nex[j][i] = -1,last=j;
else nex[j][i] = last;
}
}
for(int i=0;i<30;i++)T[i].build(1,n,nex[i],1);
for(int i=1;i<=n;i++){
for(int j=0;j<30;j++)
if((1<<j)&A[i])cnt[j][i]=cnt[j][i-1]+1,pre[j][i]=i;
else cnt[j][i]=cnt[j][i-1],pre[j][i]=pre[j][i-1];
}
while(q--){
int l,r;
scanf("%d%d",&l,&r);
auto [x,y] = solve(l,r);
printf("%d %d\n",x,y);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 77612kb
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: 220ms
memory: 83700kb
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: 293ms
memory: 79648kb
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: 0
Accepted
time: 308ms
memory: 83744kb
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:
ok 199998 numbers
Test #5:
score: -100
Wrong Answer
time: 295ms
memory: 81684kb
input:
20000 5 5 925473558 183799537 561353092 858424993 765513347 2 4 1 1 1 2 3 5 1 4 5 5 141075166 375934371 754066286 663820319 906342255 3 5 1 1 4 5 1 4 2 3 5 5 417114008 270241961 121113861 381529080 772448388 1 3 1 1 2 5 5 5 2 2 5 5 668136057 138968211 856562545 187058570 699131353 4 5 3 4 5 5 2 4 3 ...
output:
1073741823 2 1073741823 2 1073741823 2 1073741823 2 1073741823 2 1073741823 2 268435455 2 1073741823 2 1073741823 2 1073741823 2 536870911 2 536870911 2 1073741823 2 1073741823 2 536870911 2 1073741823 2 1073741823 2 1073741823 2 1073741823 2 1073741823 2 1073741823 2 1073741823 2 268435455 2 107374...
result:
wrong answer 44038th numbers differ - expected: '1', found: '2'