Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // clang-format off
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <iomanip>
- #include <bitset>
- #include <vector>
- #include <algorithm>
- #include <random>
- #include <map>
- #include <string>
- #include <set>
- #include <deque>
- #include <string>
- #include <cassert>
- using namespace std;
- const int N = 5e5+7, MOD = 1e9+7, C = 1e6;
- #define int long long
- int a[N], b[N];
- map<int, int> br;
- struct SegTree {
- vector<int> tree;
- void build(int n) {
- int h = 1;
- while (h < n) {
- h *= 2;
- }
- h *= 2;
- tree.resize(h);
- for (int i = 0; i < h; i++) {
- tree[i] = 0;
- }
- }
- void add(int v) {
- v += tree.size() / 2;
- tree[v]++;
- v /= 2;
- while (v > 0) {
- tree[v] = tree[v * 2] + tree[v * 2 + 1];
- v /= 2;
- }
- }
- int sum(int v, int l, int r, int L, int R) {
- if (L > r || R < l) {
- return 0;
- }
- if (L >= l && R <= r) {
- return tree[v];
- }
- return sum(v * 2, l, r, L, (L + R) / 2) +
- sum(v * 2+1, l, r, (L+R)/2+1, R);
- }
- int Sum(int l, int r) {
- l++;
- r++;
- return sum(1, l, r, 1, tree.size() / 2);
- }
- };
- SegTree ST;
- void solve() {
- int n, m;
- cin >> n;
- vector<pair<int, int> > b2;
- b2.clear();
- br.clear();
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- for (int i = 0; i < n; i++) {
- cin >> b[i];
- b2.push_back({ b[i], i });
- }
- cin >> m;
- for (int i = 0; i < m; i++) {
- int x;
- cin >> x;
- br[x]++;
- }
- for (int i = 0; i < n; i++) {
- if (a[i] < b[i]) {
- cout << "NO\n";
- return;
- }
- }
- ST.build(n);
- sort(b2.begin(), b2.end());
- reverse(b2.begin(), b2.end());
- for (int i = 0; i < n; i++) {
- int j = i;
- while ( j != n && b2[i].first == b2[j].first) {
- j++;
- }
- vector<int> r;
- r.clear();
- for (int k = i; k < j; k++) {
- if (a[b2[k].second] == b[b2[k].second]) {
- continue;
- }
- int L = b2[k].second, R = n;
- while (R - L > 1) {
- int mid = (L + R) / 2;
- if (ST.Sum(b2[k].second, mid) == 0) {
- L = mid;
- }
- else {
- R = mid;
- }
- }
- r.push_back(L);
- }
- sort(r.begin(), r.end());
- r.resize(unique(r.begin(), r.end()) - r.begin());
- if (r.size() > br[b2[i].first]) {
- cout << "NO\n";
- return;
- }
- for (int k = i; k < j; k++) {
- ST.add(b2[k].second);
- }
- i = j - 1;
- }
- cout << "YES\n";
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #else
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- #endif
- int t;
- cin >> t;
- while (t--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement