QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117129 | #6631. Maximum Bitwise OR | chenxinyang2006 | WA | 43ms | 9916kb | C++14 | 2.6kb | 2023-06-30 13:20:07 | 2023-06-30 13:20:11 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int T,n,q;
int a[100005],pval[100005][35];
pii res[100005];
vector <pii> Qry[100005];
struct info{
int pos,val;
};
vector <info> P[100005];
int ans[100005];
void upd(int x,int y){
while(x && ans[x] < y){
ans[x] = y;
x--;
}
}
inline int lowbit(int x) {return x & (-x);}
void recalc(int l,int r){//重新结算 [l,r] 的 ext 值
int sum = 0,tmp,pos;
per(i,r,l){
pos = i;
per(k,SZ(P[i - 1]) - 1,0){
tmp = P[i - 1][k].val | sum;
tmp |= pval[i][ctz(tmp + 1)];
upd(pos,ctz(tmp + 1));
pos = P[i - 1][k].pos - 1;
}
sum |= a[i];
}
}
void solve(){
scanf("%d%d",&n,&q);
rep(i,1,n){
scanf("%d",&a[i]);
Qry[i].clear();
ans[i] = -1;
per(k,30,0){
if(a[i] & (1 << k)) pval[i][k] = 1 << k;
else pval[i][k] = pval[i][k + 1] | (1 << k);
}
}
rep(i,1,q){
int l,r;
scanf("%d%d",&l,&r);
Qry[r].eb(mkp(l,i));
}
rep(r,1,n){
P[r].clear();
int pst = -1,pos = r;
for(info I:P[r - 1]){
if((I.val | a[r]) != I.val) chkmin(pos,I.pos);
if((I.val | a[r]) == pst) continue;
P[r].push_back({I.pos,I.val | a[r]});
pst = I.val | a[r];
}
if(pst != a[r]) P[r].push_back({r,a[r]});
recalc(max(1,pos - 1),r);
for(pii I:Qry[r]){
int tmp = 0;
for(info II:P[r]) if(II.pos <= I.first) chkmax(tmp,II.val);
// printf("%d->%d\n",I.second,tmp);
if(lowbit(tmp + 1) == tmp + 1){
res[I.second] = mkp(tmp,0);
}else if(ans[I.first] == __lg(tmp) + 1){
res[I.second] = mkp((1 << (__lg(tmp) + 1)) - 1,1);
}else{
res[I.second] = mkp((1 << (__lg(tmp) + 1)) - 1,2);
}
}
}
rep(i,1,q) printf("%d %d\n",res[i].first,res[i].second);
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9916kb
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: 39ms
memory: 9740kb
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: -100
Wrong Answer
time: 43ms
memory: 9152kb
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 1073741823 2 536870911 2 536870911 2 1073741823 2 1073741823 2...
result:
wrong answer 39th numbers differ - expected: '268435455', found: '1073741823'