Advertisement
bibaboba12345

Untitled

Jan 3rd, 2023
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.08 KB | None | 0 0
  1. // clang-format off
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <bitset>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <random>
  9. #include <map>
  10. #include <string>
  11. #include <set>
  12. #include <deque>
  13. #include <string>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17. const int N = 5e5+7, MOD = 1e9+7, C = 1e6;
  18. #define int long long
  19.  
  20. int a[N], b[N];
  21.  
  22. map<int, int> br;
  23.  
  24. struct SegTree {
  25. vector<int> tree;
  26. void build(int n) {
  27. int h = 1;
  28. while (h < n) {
  29. h *= 2;
  30. }
  31. h *= 2;
  32. tree.resize(h);
  33. for (int i = 0; i < h; i++) {
  34. tree[i] = 0;
  35. }
  36. }
  37. void add(int v) {
  38. v += tree.size() / 2;
  39. tree[v]++;
  40. v /= 2;
  41. while (v > 0) {
  42. tree[v] = tree[v * 2] + tree[v * 2 + 1];
  43. v /= 2;
  44. }
  45. }
  46. int sum(int v, int l, int r, int L, int R) {
  47. if (L > r || R < l) {
  48. return 0;
  49. }
  50. if (L >= l && R <= r) {
  51. return tree[v];
  52. }
  53. return sum(v * 2, l, r, L, (L + R) / 2) +
  54. sum(v * 2+1, l, r, (L+R)/2+1, R);
  55. }
  56. int Sum(int l, int r) {
  57. l++;
  58. r++;
  59. return sum(1, l, r, 1, tree.size() / 2);
  60. }
  61. };
  62.  
  63. SegTree ST;
  64.  
  65. void solve() {
  66. int n, m;
  67. cin >> n;
  68. vector<pair<int, int> > b2;
  69. b2.clear();
  70. br.clear();
  71. for (int i = 0; i < n; i++) {
  72. cin >> a[i];
  73.  
  74. }
  75. for (int i = 0; i < n; i++) {
  76. cin >> b[i];
  77. b2.push_back({ b[i], i });
  78. }
  79.  
  80. cin >> m;
  81. for (int i = 0; i < m; i++) {
  82. int x;
  83. cin >> x;
  84. br[x]++;
  85. }
  86. for (int i = 0; i < n; i++) {
  87. if (a[i] < b[i]) {
  88. cout << "NO\n";
  89. return;
  90. }
  91. }
  92. ST.build(n);
  93. sort(b2.begin(), b2.end());
  94. reverse(b2.begin(), b2.end());
  95. for (int i = 0; i < n; i++) {
  96. int j = i;
  97. while ( j != n && b2[i].first == b2[j].first) {
  98. j++;
  99. }
  100. vector<int> r;
  101. r.clear();
  102. for (int k = i; k < j; k++) {
  103. if (a[b2[k].second] == b[b2[k].second]) {
  104. continue;
  105. }
  106. int L = b2[k].second, R = n;
  107. while (R - L > 1) {
  108. int mid = (L + R) / 2;
  109. if (ST.Sum(b2[k].second, mid) == 0) {
  110. L = mid;
  111. }
  112. else {
  113. R = mid;
  114. }
  115. }
  116. r.push_back(L);
  117. }
  118. sort(r.begin(), r.end());
  119. r.resize(unique(r.begin(), r.end()) - r.begin());
  120. if (r.size() > br[b2[i].first]) {
  121. cout << "NO\n";
  122. return;
  123. }
  124. for (int k = i; k < j; k++) {
  125. ST.add(b2[k].second);
  126. }
  127. i = j - 1;
  128. }
  129. cout << "YES\n";
  130. }
  131.  
  132. signed main() {
  133. #ifdef _DEBUG
  134. freopen("input.txt", "r", stdin);
  135. #else
  136. std::ios::sync_with_stdio(false);
  137. cin.tie(0);
  138. #endif
  139. int t;
  140. cin >> t;
  141. while (t--) {
  142. solve();
  143. }
  144. }
  145.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement