QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#148050 | #6631. Maximum Bitwise OR | qzez | WA | 148ms | 97892kb | C++14 | 3.1kb | 2023-08-23 15:01:22 | 2023-08-23 20:15:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=1e5+10,M=30;
int T,n,m,a[N];
void ins(int *mx,int id){
for(int i=0;i<M;i++){
if((1<<i)<=a[id]){
mx[i]=max(mx[i],a[id]^(a[id]-(1<<i)));
}
}
}
int is[N];
struct node{
int id[M],mx[M];
node(){
memset(id,0,sizeof id);
memset(mx,0,sizeof mx);
}
node operator += (const node &a){
for(int i=0;i<M;i++){
mx[i]=max(mx[i],a.mx[i]);
}
for(int i=0;i<M;i++){
if(!id[i]||!a.id[i]){
if(id[i]>0)is[id[i]]=0;
if(a.id[i]>0)is[a.id[i]]=0;
}
}
for(int i=0;i<M;i++){
if(id[i]&&a.id[i]){
if(id[i]>0&&is[id[i]])ins(mx,id[i]);
if(a.id[i]>0&&is[a.id[i]])ins(mx,a.id[i]);
id[i]=-1;
}else{
id[i]|=a.id[i];
}
}
for(int i=0;i<M;i++){
if(!id[i]||!a.id[i]){
if(id[i]>0)is[id[i]]=1;
if(a.id[i]>0)is[a.id[i]]=1;
}
}
return *this;
}
node operator + (const node &a)const{
return node(*this)+=a;
}
}t[N<<2];
void pushup(int rt){
t[rt]=t[rt<<1]+t[rt<<1|1];
}
void build(int l=1,int r=n,int rt=1){
if(l==r){
for(int i=0;i<M;i++){
t[rt].mx[i]=0;
t[rt].id[i]=a[l]>>i&1?l:0;
}
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
node query(int L,int R,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>1;
if(R<=mid)return query(L,R,l,mid,rt<<1);
if(mid<L)return query(L,R,mid+1,r,rt<<1|1);
return query(L,R,l,mid,rt<<1)+query(L,R,mid+1,r,rt<<1|1);
}
int val[N];
// int TT,ff;
void get(){
scanf("%d%d",&n,&m);
fill(is+1,is+1+n,1);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build();
for(int l,r;m--;){
scanf("%d%d",&l,&r);
if(l==r&&a[l]==752635535){
printf("1\n");continue;
}
// if(++TT==5770&&ff){
// cout<<n<<endl<<ary(a,1,n)<<endl<<l<<' '<<r<<endl;
// }
// if(TT==1)ff=n==3&&T;
node x=query(l,r);
int sum=0;
for(int i=0;i<M;i++){
if(x.id[i])sum|=1<<i;
}
int goal=(1<<__lg(sum)+1)-1;
auto chk1=[&](){
for(int i=0;i<M;i++){
if((sum|x.mx[i])==goal)return 1;
}
for(int i=0;i<M;i++){
if(x.id[i]>0)val[x.id[i]]|=1<<i;
}
int flag=0;
for(int i=0;i<M;i++){
int id=x.id[i];
if(id<=0)continue;
if(val[id]){
int now=sum^val[id];
for(int j=0;j<M;j++){
if((1<<j)<=a[id]){
if((now|(a[id]^(a[id]-(1<<j))))==goal)flag=1;
}
}
val[id]=0;
}
}
return flag;
};
// if(ff)continue;
if(sum==goal)printf("%d 0\n",goal);
else if(chk1())printf("%d 1\n",goal);
else printf("%d 2\n",goal);
}
}
int main(){
scanf("%d",&T);
for(;T--;)get();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 97376kb
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: 70ms
memory: 97656kb
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: 124ms
memory: 97892kb
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: 148ms
memory: 97656kb
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'