oj.uz

Submission #477453

# Submission time Handle Problem Language Result Execution time Memory
477453 2021-10-02T07:50:38 Z hhhhaura Bitwise (BOI06_bitwise) C++14
100 / 100
 1 ms 216 KB 
#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, 0);
			rep(j, L, R) {
				if(ans[j] + (1ll << x) <= B[j]) a[j] |= 2;
				if(ans[j] + (1ll << 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] |= (1ll << x);
				if(a[j] == 3 && !cnt[2] && !(cnt[3] - 1)) ans[j] |= (1ll << x), cnt[3] --;
			}
		}
		int mask = (1ll << 31) - (1ll << x) - 1;
		if(!val) rep(i, 1, n) if(a[i] == 3) ans[i] &= mask;
		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

bitwise.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      |

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 216 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct