Dang_Quan_10_Tin

THT C (2021) badmi

Oct 16th, 2021
467
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. constexpr int N = 1e5 + 5;
  6. pair<int, int> a[N], b[N];
  7. int n, m, q, id[N];
  8.  
  9. void Read()
  10. {
  11.     cin >> n >> m >> q;
  12.     for (int i = 1; i <= n; ++i)
  13.         cin >> a[i].first;
  14.     for (int i = 1; i <= n; ++i)
  15.         cin >> a[i].second;
  16.     for (int i = 1; i <= m; ++i)
  17.         cin >> b[id[i] = i].first;
  18.     for (int i = 1; i <= m; ++i)
  19.         cin >> b[i].second;
  20. }
  21.  
  22. void Solve()
  23. {
  24.     sort(a + 1, a + n + 1);
  25.  
  26.     while (q--)
  27.     {
  28.         int k;
  29.         cin >> k;
  30.  
  31.         sort(id + k, id + k + n, [&](const int &x, const int &y)
  32.              { return b[x] < b[y]; });
  33.         multiset<int> s;
  34.         int ans(0);
  35.  
  36.         for (int i = 1, j = k; i <= n; ++i)
  37.         {
  38.             while (j < k + n && b[id[j]].first < a[i].first)
  39.             {
  40.                 s.insert(b[id[j]].second);
  41.                 //cerr << "jump: " << i << " " << j << "\n";
  42.                 ++j;
  43.             }
  44.  
  45.             auto t = s.lower_bound(a[i].second);
  46.             if (t != s.begin())
  47.             {
  48.                 ++ans;
  49.                 s.erase(prev(t));
  50.             }
  51.         }
  52.  
  53.         cout << ans << '\n';
  54.  
  55.         for (int j = k + n - 1; j >= k; --j)
  56.             id[j] = j;
  57.     }
  58. }
  59.  
  60. int32_t main()
  61. {
  62.     ios::sync_with_stdio(0);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.     Read();
  66.     Solve();
  67. }
RAW Paste Data