QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#375567 | #6631. Maximum Bitwise OR | wsc2008 | WA | 297ms | 212728kb | C++14 | 2.5kb | 2024-04-03 13:06:02 | 2024-04-03 13:06:03 |
Judging History
answer
#include<bits/stdc++.h>
typedef int ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const ll N=1e5+9;
ll T,n,q,a[N],sum[31][N],pos[31][N],cnt[31];
ll f[466][N],bin[31][31],id[31][31],tid;
bool debug=1;
ll cq;
vector<ll>spe[N];
void solve(ll tid){
n=read(),q=read();
if(tid==1)debug&=(n==3&&q==3);
rep(i,1,n)a[i]=read();
if(debug&&tid==1553){
rep(i,1,n)cout<<a[i]<<" ";
cout<<endl;
}
rep(i,0,30){
rep(j,0,n)sum[i][j]=pos[i][j]=0;
}
rep(i,0,465){
rep(j,0,n)f[i][j]=0;
}
rep(i,0,30){
rep(j,1,n){
sum[i][j]=sum[i][j-1]+((a[j]>>i)&1);
pos[i][j]=pos[i][j-1]+((a[j]>>i)&1)*j;
}
}
rep(i,1,n){
memset(bin,0,sizeof(bin));
ll cur=30;
per(j,30,0){
if((a[i]>>j)&1)cur=j;
if(cur<30){
rep(k,j,cur)bin[j][k]=1;
}
}
cur=0;
rep(j,0,30){
rep(k,j,30)f[cur++][i]=bin[j][k];
}
}
rep(i,0,465){
rep(j,1,n)f[i][j]+=f[i][j-1];
}
while(q--){
ll l=read(),r=read(),top=30;
if(debug&&tid==1553)cout<<l<<" "<<r<<endl;
while(top>=0&&sum[top][r]-sum[top][l-1]==0)top--;
if(!(~top)){
if(!debug)puts("0 0");
continue;
}
if(!debug)write((2<<top)-1),putchar(' ');
rep(i,0,top)cnt[i]=sum[i][r]-sum[i][l-1];
vector<ll>tar;
ll L=31,R=-1;
rep(i,0,top){
if(cnt[i]==1){
ll p=pos[i][r]-pos[i][l-1];
tar.push_back(p);
spe[p].push_back(i);
}
if(!cnt[i])L=min(L,i),R=max(R,i);
}
if(L>R){
if(!debug)puts("0");
for(ll i:tar)spe[i].clear();
continue;
}
sort(tar.begin(),tar.end());
tar.resize(unique(tar.begin(),tar.end())-tar.begin());
ll rid=id[L][R],qq=f[rid][r]-f[rid][l-1];
for(ll i:tar){
sort(spe[i].begin(),spe[i].end());
ll st=f[rid][i]-f[rid][i-1];
qq-=st;
ll nid=id[min(spe[i][0],L)][max(spe[i].back(),R)];
qq+=f[nid][i]-f[nid][i-1];
}
if(!debug){
if(qq)puts("1");
else puts("2");
}
for(ll i:tar)spe[i].clear();
}
}
bool Med;
int main(){
cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
rep(i,0,30){
rep(j,i,30)id[i][j]=++tid;
}
T=read();
debug&=(T==33333);
rep(tid,1,T)solve(tid);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 212728kb
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: 297ms
memory: 212376kb
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: 203ms
memory: 211704kb
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: 175ms
memory: 210944kb
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:
169019744 945504599 369619596 1 2 2 3 2 3
result:
wrong answer 1st numbers differ - expected: '536870911', found: '169019744'