QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122695#6631. Maximum Bitwise ORinstallb#WA 308ms83744kbC++142.9kb2023-07-10 22:20:582023-07-10 22:21:00

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-10 22:21:00]
  • 评测
  • 测评结果:WA
  • 用时:308ms
  • 内存:83744kb
  • [2023-07-10 22:20:58]
  • 提交

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'