QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127904 | #6631. Maximum Bitwise OR | yy_zq | WA | 240ms | 13876kb | C++14 | 3.9kb | 2023-07-20 11:17:13 | 2023-07-20 11:17:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;++i)
#define For(i,j,k) for(int i=j;i>=k;--i)
#define mid (l+r>>1)
const int MAX = 1e5+111;
const int D = 30;
const int INF = 31;
int a[MAX];
int S[MAX][33];
int pos[MAX][33];//表示从某一位开始最后一个连续 0 的位置
int mn[MAX*4][33];//表示右侧节点大于 x 的最小左端点
int who[MAX*4][33];//特殊数的位置
int cnt[MAX*4][33];//统计每个数字出现的次数,以寻找特殊数
//线段树查询存储答案的数组
int que[33];
int que_who[33];
int used[MAX];//判断一个数是否多次作为 special 出现
void build(int l,int r,int x){
if(l==r){
FOR(i,0,D){
cnt[x][i] = S[l][i];
who[x][i] = l;
mn[x][i] = pos[l][i];
}
return;
}
build(l,mid,x<<1),build(mid+1,r,x<<1|1);
FOR(i,0,D){
cnt[x][i] = cnt[x<<1][i]+cnt[x<<1|1][i];
if(cnt[x<<1][i]) who[x][i] = who[x<<1][i];
else who[x][i]=who[x<<1|1][i];
mn [x][i] =min( mn[x<<1][i], mn[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,D){
que[i]+=cnt[x][i];
if(cnt[x][i]) que_who[i] = who[x][i];
}
return;
}
ask(l,mid,x<<1,lft,rht),ask(mid+1,r,x<<1|1,lft,rht);
}
int ask_min(int l,int r,int x,int lft,int rht,int dig){
if(l>rht||r<lft) return INF;
if(l>=lft&&r<=rht){
return mn[x][dig];
}
return min(ask_min(l,mid,x<<1,lft,rht,dig),ask_min(mid+1,r,x<<1|1,lft,rht,dig));
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in","r",stdin);
int t;
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
FOR(i,1,n) cin>>a[i];
//第一步预处理
FOR(i,1,n){
int mx=0;
FOR(j,0,D){
if((a[i])&(1ll<<j)){
S[i][j]=1;
mx = j;
}
else S[i][j] = 0;
}
int lst = 0;
FOR(j,0,mx){
if((a[i])&(1ll<<j)){
pos[i][j] = lst;
lst = j+1;
}
else pos[i][j] = lst;
}
FOR(j,mx+1,D) pos[i][j] = 31;
}
//建树
build(1,n,1);
while(q--){
int l,r;
cin>>l>>r;
FOR(i,0,D) que[i] = 0;
ask(1,n,1,l,r);
//信息提取完成
int max_or=0,max_dig=0;
For(i,30,0){
if(que[i]){
max_or = (1ll<<(i+1))-1;
max_dig = i;
break;
}
}
int tmpys=1;
For(i,max_dig,0){
if(!que[i]) tmpys=0;
}
if(tmpys){
cout<<max_or<<' '<<0<<endl;
continue;
}
else{
int special_num[33]={};
int special_cnt=0;
For(i,30,0){
if(que[i]==1){
special_num[++special_cnt] = que_who[i];
used[que_who[i]]++;
}
}
sort(special_num+1,special_num+1+special_cnt);
special_cnt = unique(special_num+1,special_num+1+special_cnt) - special_num -1;
//因为special 是不能选的,因此边界要处理一下,才能一起处理
special_num[0] = l-1;
special_num[special_cnt+1] = r+1;
//下面查询区间贡献
int ys = 1;
For(i,max_dig,0){
if(!que[i]){
int mn_dig=INF;
FOR(j,0,special_cnt){
int tmp_min =ask_min(1,n,1,special_num[j]+1,special_num[j+1]-1,i+1);
mn_dig = min(tmp_min,mn_dig);
}
For(j,mn_dig-1,0){
if(!que[j]){
ys=0;
break;
}
}
break;
}
}
if(ys){
cout<<max_or<<' '<<1<<endl;
}
else{
//此时需要查验特殊数字
int mn_0=0;
FOR(i,0,D){
if(que[i]==0){
mn_0 = 0;
break;
}
}
int ys2 = 0;
For(i,max_dig,0){
if(que[i]==0) break;
if(que[i]==1){
if(used[que_who[i]]==1){
if(pos[que_who[i]][i]<=mn_0){
ys2=1;
break;
}
}
}
}
if(ys2) cout<<max_or<<' '<<1<<endl;
else cout<<max_or<<' '<<2<<endl;
}
FOR(i,1,special_cnt){
used[special_num[i]] = 0;
}
}
}
}
return 0;
}
/*
1
4 2
12 1 1 12
1 4
1 4
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 11632kb
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: 170ms
memory: 13876kb
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: 169ms
memory: 11668kb
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: 240ms
memory: 11688kb
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 9322nd numbers differ - expected: '1', found: '2'