Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- #define pb emplace_back
- #define AI(i) begin(i), end(i)
- template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
- template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
- #ifdef KEV
- #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
- void kout() { cerr << endl; }
- template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
- template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
- #else
- #define DE(...) 0
- #define debug(...) 0
- #endif
- // My bug list :
- // integer overflow
- // 0based, 1based forgotten
- // index out of bound
- // n, m, i, j typo
- // some cases are missing
- const int MAX_N = 300010, LG = 31, inf = 1e9;
- int dp[MAX_N][2][2];
- void solve() {
- int n;
- cin >> n;
- vector<int> a(n), b(n);
- for (int &i : a) cin >> i;
- for (int &i : b) cin >> i;
- a.pb(0);
- // I want to know if team B can win
- // if values are the same, team A always win
- // j means number of team A removed
- // k means number of team B removed
- for (int j : {0, 1}) for (int k : {0, 1})
- dp[n][j][k] = (k == 1 ? inf : n * LG);
- // yes, it's n * LG
- for (int i = n-1;i >= 0;--i) {
- for (int j : {0, 1}) for (int k : {0, 1}) {
- dp[i][j][k] = inf;
- int l = 0, r = n * LG, m;
- auto valid = [&](int index) {
- // First we consider when k = 1 and we remove this one.
- if (k == 1 && dp[i+1][j][k-1] <= index)
- return true;
- // Then we are now sure that we keep b[i]
- int id = index / LG, t = index % LG, cv = b[i];
- while (id < n && cv > (a[id] >> t)) {
- ++id, t = 0, cv >>= 1;
- }
- int nxt = id * LG + t + 1;
- // case 1 : keep the id-th item
- if (dp[i+1][j][k] <= nxt)
- return true;
- // case 2 : remove id from team A
- if (j == 0) return false;
- id = min(n, id + 1), t = 0;
- while (id < n && cv > a[id]) {
- ++id, cv >>= 1;
- }
- return dp[i+1][0][k] <= id * LG + 1;
- };
- while (l < r) {
- m = l + r >> 1;
- if (valid(m))
- r = m;
- else
- l = m+1;
- }
- dp[i][j][k] = l;
- }
- }
- cout << (dp[0][1][1] == 0 ? "Yes" : "No") << '\n';
- }
- int32_t main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- int T;
- cin >> T;
- while (T--)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement