# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
477443 | hhhhaura | Bitwise (BOI06_bitwise) | C++14 | 1 ms | 204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define int long long int
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
namespace solver {
int n, p;
vector<int> A, B, st, sz, ans, a;
void init_(int _n, int _p) {
n = _n, p = _p;
A.assign(n + 1, 0);
B.assign(n + 1, 0);
st.assign(p + 1, 1);
sz.assign(p + 1, 0);
ans.assign(n + 1, 0);
a.assign(n + 1, 0);
}
int operate(int x) {
int val = 1;
a.assign(n + 1, 0);
rep(i, 1, p) {
int L = st[i], R = st[i] + sz[i] - 1;
vector<int> cnt(4);
rep(j, L, R) {
if(ans[j] + (1 << x) <= B[j]) a[j] |= 2;
if(ans[j] + (1 << x) - 1 >= A[j]) a[j] |= 1;
cnt[a[j]] ++;
}
val &= (cnt[2] || cnt[3]);
rep(j, L, R) {
if(a[j] == 2) ans[j] |= (1 << x);
if(a[j] == 3 && !cnt[2] && !(cnt[3] - 1)) ans[j] |= (1 << x), cnt[3] --;
}
}
return val;
}
int solve() {
int val = 0;
rrep(i, 0, 31) val |= (operate(i) << i);
return val;
}
};
using namespace solver;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, p;
cin >> n >> p;
init_(n, p);
rep(i, 1, p) {
st[i] = st[i - 1] + sz[i - 1];
cin >> sz[i];
}
rep(i, 1, n) cin >> A[i] >> B[i];
cout << solve() << "\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |