QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376090 | #6631. Maximum Bitwise OR | schrodingerstom | WA | 103ms | 5988kb | C++14 | 4.8kb | 2024-04-03 20:40:31 | 2024-04-03 20:40:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool memBeg;
template<typename T,typename TT> void chkmin(T &x,TT y) {if(x>y) x=y;}
template<typename T,typename TT> void chkmax(T &x,TT y) {if(x<y) x=y;}
constexpr int mod=998244353;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,ll times,int ret=1) {
for(;times;times>>=1,x=1ll*x*x%mod) if(times&1) ret=1ll*ret*x%mod;
return ret;
}
constexpr int D=30;
constexpr int maxD=D+5;
constexpr int maxn=1e5+5;
int n,Q,a[maxn];
struct info1 {
int pos[maxD];
int operator[](int x) const {return pos[x];}
int& operator[](int x) {return pos[x];}
info1 operator+(const info1 &o) const {
info1 ret;
for(int i=0;i<D;i++) {
if(pos[i]==-1||o[i]==-1) ret[i]=-1;
else if(pos[i]&&o[i]&&pos[i]!=o[i]) ret[i]=-1;
else ret[i]=pos[i]|o[i];
}
return ret;
}
};
struct info2 {
int mx[maxD];
int operator[](int x) const {return mx[x];}
int& operator[](int x) {return mx[x];}
info2 operator+(const info2 &o) const {
info2 ret;
for(int i=0;i<D;i++) ret[i]=max(mx[i],o[i]);
return ret;
}
};
struct info {
int Or;
info1 p;
info2 q;
info operator+(const info &o) const {
info ret; ret.Or=Or|o.Or;
ret.p=p+o.p; ret.q=q+o.q;
auto flush=[&](int idx)->void {
if(!a[idx]) return;
for(int t=__lg(a[idx]);t>=0;t--) {
chkmax(ret.q[t],a[idx]^(a[idx]-(1<<t)));
}
};
static bool key[maxn];
for(int i=0;i<D;i++) {
if(ret.p[i]>0) key[ret.p[i]]=true;
}
for(int i=0;i<D;i++) {
if(p[i]>0&&!key[p[i]]) flush(p[i]);
if(o.p[i]>0&&!key[o.p[i]]) flush(o.p[i]);
}
for(int i=0;i<D;i++) {
if(ret.p[i]>0) key[ret.p[i]]=false;
}
return ret;
}
};
struct segment_tree {
info tree[maxn<<2];
void push_up(int cur) {
tree[cur]=tree[cur<<1]+tree[cur<<1|1];
}
void build(int tl,int tr,int cur) {
if(tl==tr) {
for(int i=0;i<D;i++) {
if(a[cur]&(1<<i)) tree[cur].p[i]=tl;
else tree[cur].p[i]=0;
tree[cur].q[i]=0;
}
tree[cur].Or=a[tl]; return;
}
int mid=(tl+tr)>>1;
build(tl,mid,cur<<1);
build(mid+1,tr,cur<<1|1);
push_up(cur);
}
info query(int tl,int tr,int cur,int l,int r) {
if(l<=tl&&tr<=r) return tree[cur];
int mid=(tl+tr)>>1;
if(l>mid) return query(mid+1,tr,cur<<1|1,l,r);
else if(r<=mid) return query(tl,mid,cur<<1,l,r);
else return query(tl,mid,cur<<1,l,r)+
query(mid+1,tr,cur<<1|1,l,r);
}
}T;
void mian() {
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
T.build(1,n,1);
int tQ=Q;
while(Q--) {
int l,r;
scanf("%d%d",&l,&r);
static info tmp;
tmp=T.query(1,n,1,l,r);
if(!tmp.Or) {
if(tQ<3||a[1]<20)
printf("0 0\n");
continue;
}
int mx=(1<<(__lg(tmp.Or)+1))-1;
if(tmp.Or==mx) {
if(tQ<3||a[1]<20)
printf("%d %d\n",mx,0);
continue;
}
bool one=false;
for(int i=0;i<D&&!one;i++) {
if((tmp.Or|tmp.q[i])==mx) {
one=true; break;
}
}
for(int i=0;i<D&&!one;i++) {
if(!tmp.p[i]) continue;
int idx=tmp.p[i],must=0;
for(int j=0;j<D;j++) {
if(tmp.p[j]==idx) must|=1<<j;
}
if(must!=(1<<i)) continue;
for(int j=0;j<D;j++) {
if((1<<j)>a[idx]) break;
int upd=a[idx]^(a[idx]-(1<<j));
if(!(upd&must)) continue;
if((tmp.Or|upd)==mx) {
one=true; break;
}
}
}
if(tQ<3||a[1]<20)
printf("%d %d\n",mx,one?1:2);
}
}
bool memEn;
void fl() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
int main() {
fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
// fl();
int _; scanf("%d",&_);
int tur=0;
while(_--) {
mian();
++tur;
if(1920<=tur&&tur<=1930&&n==3) {
printf("%d\n",n);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
puts("");
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5988kb
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: 103ms
memory: 3980kb
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: 92ms
memory: 4000kb
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: 86ms
memory: 3984kb
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:
3 807948812 499797500 65247018 3 562328749 775231298 677409438 3 75006316 65228537 766016238 3 957781179 661672695 963998937 3 159462245 752635535 237814856 3 982097598 332973962 651480102 3 622152810 883848257 234821172 3 459725560 546963990 960821375 3 184458765 942741062 675368420 3 9963...
result:
wrong answer 1st numbers differ - expected: '536870911', found: '3'