QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#114987 | #6631. Maximum Bitwise OR | applese | WA | 150ms | 10760kb | C++14 | 3.4kb | 2023-06-24 13:15:31 | 2023-06-24 13:15:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int T, n, q, a[maxn];
#define lc (o << 1)
#define rc (o << 1 | 1)
#define mid ((l + r) >> 1)
#define lson lc, l, mid
#define rson rc, mid + 1, r
struct Node {
int v, high;
Node(int v = 0, int high = -1) : v(v), high(high) {}
void Init(int x) {
v = x;
high = -1;
if(x) {
high = 0;
while((1 << high) <= x)
++ high;
-- high;
}
}
}tror[maxn << 2];
Node Merge(Node a, Node b) {
return Node(a.v | b.v, max(a.high, b.high));
}
int Mer(int a, int b) {
if(a == -1 || b == -1 || (a > 0 && b > 0))
return -1;
if(a > 0 && b == 0)
return a;
if(b > 0 && a == 0)
return b;
return 0;
}
int arr[maxn << 2][32], cnt[maxn << 2][32];
void Build(int o, int l, int r) {
if(l == r) {
tror[o].Init(a[l]);
vector<int> v;
v.clear();
v.push_back(-1);
memset(cnt[o], 0, sizeof cnt[o]);
for(int j = 0; j < 30; ++ j)
if(a[l] >> j & 1) {
v.push_back(j);
cnt[o][j] = l;
}
memset(arr[o], 0x3f, sizeof arr[o]);
for(int j = 0; j + 1 < (int)v.size(); ++ j) {
int lp = v[j] + 1, rp = v[j + 1];
// cerr << "Pos: " << l << " " << lp << " " << rp << endl;
for(int x = lp; x <= rp; ++ x) {
arr[o][x] = lp;
}
}
return;
}
Build(lson), Build(rson);
tror[o] = Merge(tror[lc], tror[rc]);
for(int j = 0; j < 32; ++ j) {
arr[o][j] = min(arr[lc][j], arr[rc][j]);
cnt[o][j] = Mer(cnt[lc][j], cnt[rc][j]);
}
}
Node Get(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr)
return tror[o];
Node x;
if(ql <= mid)
x = Merge(x, Get(lson, ql, qr));
if(qr > mid)
x = Merge(x, Get(rson, ql, qr));
return x;
}
int Ask(int o, int l, int r, int ql, int qr, int rp) {
if(ql > qr)
return 1e9;
if(ql <= l && r <= qr)
return arr[o][rp];
int x = 1e9;
if(ql <= mid)
x = min(x, Ask(lson, ql, qr, rp));
if(qr > mid)
x = min(x, Ask(rson, ql, qr, rp));
return x;
}
int Que(int o, int l, int r, int ql, int qr, int pos) {
if(ql <= l && r <= qr)
return cnt[o][pos];
int x = 0;
if(ql <= mid)
x = Mer(x, Que(lson, ql, qr, pos));
if(qr > mid)
x = Mer(x, Que(rson, ql, qr, pos));
return x;
}
vector<int> v;
int main() {
for(scanf("%d", &T); T --; ) {
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
}
Build(1, 1, n);
for(int l, r; q --; ) {
scanf("%d%d", &l, &r);
Node now = Get(1, 1, n, l, r);
// cerr << now.v << " " << now.high << endl;
assert(now.v < (1 << (now.high + 1)));
if(now.v == ((1 << (now.high + 1)) - 1)) {
printf("%d %d\n", now.v, 0);
continue;
}
int lx = 31, rx = -1;
for(int i = 0; i <= now.high; ++ i) {
if(!(now.v >> i & 1)) {
lx = min(lx, i);
rx = max(rx, i);
}
}
assert(lx <= rx);
v.clear();
v.push_back(l - 1);
v.push_back(r + 1);
for(int i = 0; i <= now.high; ++ i) {
int p = Que(1, 1, n, l, r, i);
if(p > 0) {
v.push_back(p);
}
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int x = 1e9;
for(int i = 0; i + 1 < (int)v.size(); ++ i)
x = min(x, Ask(1, 1, n, v[i] + 1, v[i + 1] - 1, rx));
// cerr << p << " " << x << " " << lx << " " << rx << endl;
// cerr << Ask(1, 1, n, l, r, rx) << " " << now.v << " " << lx << " " << rx << endl;
printf("%d %d\n", ((1 << (now.high + 1)) - 1), 1 + (x > lx));
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10144kb
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: 116ms
memory: 10072kb
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: 118ms
memory: 10100kb
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: 150ms
memory: 10760kb
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 9322nd numbers differ - expected: '1', found: '2'