QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122754 | #6631. Maximum Bitwise OR | wnmrmr# | RE | 0ms | 0kb | C++23 | 4.1kb | 2023-07-11 01:39:34 | 2023-07-11 01:39:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#define pb push_back
#define int long long
int n, q;
void solve () {
cin >> n >> q;
vector<int> a (n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector last (n + 1, vector<int> (30));
vector sum_bit (n + 1, vector<int> (30));
vector freq (n + 1, vector (30, vector<int> (30)));
vector acum (n + 1, vector (30, vector<int> (30)));
for (int i = 1; i <= n; i++) {
last[i] = last[i - 1];
sum_bit[i] = sum_bit[i - 1];
acum[i] = acum[i - 1];
// vamos adicionar o numero
for (int l = 0; l < 30; l++) {
// atualizamos o ultimo
if ((1 << l) & a[i]) last[i][l] = i, sum_bit[i][l]++;
// atualizamos freq
freq[i][l][l]++;
for (int r = l + 1; r < 30; r++) {
if ((1 << r) & a[i]) break;
else freq[i][l][r]++;
}
}
for (int l = 0; l < 30; l++)
for (int r = l; r < 30; r++)
acum[i][l][r] += freq[i][l][r];
}
auto get_f = [&] (int l, int r) {
vector f (30, vector<int> (30));
for (int i = 0; i < 30; i++)
for (int j = i; j < 30; j++)
f[i][j] = acum[r][i][j] - acum[l - 1][i][j];
return f;
};
auto get_sum = [&] (int l, int r) {
vector<int> sum (30);
for (int i = 0; i < 30; i++) sum[i] = sum_bit[r][i] - sum_bit[l - 1][i];
return sum;
};
while (q--) {
int l, r; cin >> l >> r;
auto f = get_f (l, r);
auto sum = get_sum (l, r);
int mx = 29;
while (mx >= 0 && !sum[mx]) mx--;
// dbg (mx);
cout << (1 << (mx + 1)) - 1 << " ";
if (mx < 0) {
// se o or eh 0
cout << "0\n";
continue;
}
bool ok = true;
for (int j = 0; j <= mx; j++) if (!sum[j]) ok = false;
if (ok) {
cout << "0\n";
continue;
}
// senao, temos que ver se a resposta eh 1
// vamos fazer operacao com cada cara 1, e depois vamos ver
vector<int> esp;
for (int j = 0; j < 30; j++) if (sum[j] == 1) {
// se esse cara eh unico
esp.pb (last[r][j]);
}
sort (all (esp));
esp.resize (unique (all (esp)) - esp.begin ());
ok = false;
for (auto id : esp) {
// retiramos e vermos se eh possivel
for (int i = 0; i < 30; i++) for (int j = i; j < 30; j++)
f[i][j] -= freq[id][i][j];
// temos que ver se ainda existe um cara que preenche
int esq = 30, dir = -1;
for (int j = 0; j <= mx; j++) if (!f[j][j]) {
esq = min (esq, j);
dir = max (dir, j);
}
if (freq[id][esq][dir]) {
ok = true;
}
for (int i = 0; i < 30; i++) for (int j = i; j < 30; j++)
f[i][j] += freq[id][i][j];
}
if (ok) {
cout << "1\n";
continue;
}
for (auto id : esp) {
// retiramos e vermos se eh possivel
for (int i = 0; i < 30; i++) for (int j = i; j < 30; j++)
f[i][j] -= freq[id][i][j];
}
int esq = 30, dir = -1;
for (int j = 0; j <= mx; j++) if (!f[j][j]) {
esq = min (esq, j);
dir = max (dir, j);
}
if (f[esq][dir]) {
ok = true;
}
if (ok) {
cout << "1\n";
continue;
}
cout << "2\n";
}
}
signed main () {
ios::sync_with_stdio(0);cin.tie(0);
int t; cin >> t;
while (t--)
solve ();
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
1 3 2 10 10 5 1 2 1 3