| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1303499 | AverageAmogusEnjoyer | Bitwise (BOI06_bitwise) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);
int rng() {
return ui(mrand);
}
constexpr int LOG = 30;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<int> v(m);
for (int &x: v)
cin >> x;
vector<array<int,2>> ranges(n);
for (auto &[a,b]: ranges)
cin >> a >> b;
vector<vector<array<int,2>>> groups(m);
for (int i = 0, j = 0, t = 0; i < n; i++) {
if (j == v[t])
j = 0,t++;
groups[t].push_back(ranges[i]);
j++;
}
int res = 0;
auto can_do = [&](vector<array<int,2>> w,int x) {
for (int bit = LOG; bit >= 0; bit--) {
// invariante: gli [a,b] sono contenuti in [0,2^(bit + 1) - 1]
vector<int> ones,zeros;
for (int i = 0; i < w.size(); i++) {
auto [a,b] = w[i];
if (b == (1LL << (bit + 1)) - 1)
return true;
if ((a >> bit) & 1) {
ones.push_back(i);
} else if (b >= (1 << bit)) {
zeros.push_back(i);
}
}
if (zeros.size() >= 2 || (zeros.size() >= 1 && ones.size() >= 1))
return true;
if (!((x >> bit) & 1)) {
if (zeros.size() >= 1) return true;
for (int idx: ones) {
w[idx][0] -= 1 << bit;
w[idx][1] -= 1 << bit;
}
continue;
}
// zeros.size() è 0 o 1; se è 1, è l'unico candidato
if (zeros.size() == 1) {
w[zeros[0]][1] -= 1 << bit;
w[zeros[0]][0] = 0;
} else {
if (ones.empty()) return false;
for (int idx: ones) {
w[idx][0] -= 1 << bit;
w[idx][1] -= 1 << bit;
}
}
}
return true;
};
auto can = [&](int x) {
for (auto w: groups)
if (!can_do(w,x))
return false;
return true;
};
for (int bit = LOG; bit >= 0; bit--) {
if (can(res | (1 << bit)))
res |= (1 << bit);
}
cout << res << "\n";
}