QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#176922 | #6631. Maximum Bitwise OR | UNos_maricones | WA | 114ms | 14152kb | C++20 | 2.4kb | 2023-09-12 10:26:28 | 2023-09-12 10:26:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std ;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double lf;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll SQ = 800;
const ll N = 1e5+5;
const ll mod = 998244353;
const ll oo = 1e18;
vector <int> hv[30][30];
int psum[30][N];
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector <int> a(n);
for (auto &e : a) cin >> e;
for(int j =0;j<30;++j){
for(int k=0;k<30;++k) hv[j][k].clear();
}
for (int i = 0; i < n; ++i) {
for (int j = 29; j >= 0; --j) {
if (i) psum[j][i] = psum[j][i-1];
else psum[j][i]=0;
}
for (int j = 29; j >= 0; --j) {
if (a[i] & (1<<j)) {
psum[j][i]++;
int sj = j;
while (j > 0 && (a[i] & (1<<(j-1))) > 0) j--;
for (int k = sj; k >= j; --k) {
for(int h = k; h >= j; --h) hv[k][h].pb(i);
}
}
}
}
for (int i = 0; i < q; i++) {
int l,r; cin >> l >> r;
r--;l--;
int yet = 0;
int mx = -1, mn;
int unq = (1<<30)-1;
int pp = -1;
for (int j = 29; j >= 0; --j) {
int v = psum[j][r] - (l ? psum[j][l-1] : 0);
if (v >= 1) {
if (v == 1) unq ^= (1<<j);
yet=1;
pp = max(pp, j);
}
else {
if (yet) {
if (mx == -1) mx = j;
mn = j;
}
}
}
int desired = (1 << (pp+1))-1;
if (mx == -1) cout << desired << " " << 0 << '\n';
else {
int fs = lower_bound(hv[mx][mn].begin(), hv[mx][mn].end(), l) - hv[mx][mn].begin();
int can = 2;
while (fs < hv[mx][mn].size() && hv[mx][mn][fs] <= r) {
int idx = hv[mx][mn][fs];
if ((unq & a[idx]) == a[idx]) {
can = 1;
break;
}
fs++;
}
cout << desired << ' ' << can << '\n';
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 14136kb
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: 114ms
memory: 11936kb
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: 92ms
memory: 14152kb
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:
wrong answer 36426th numbers differ - expected: '0', found: '2'