Advertisement
sasa2742002

Untitled

Dec 20th, 2022
823
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. #define T     \
  7.   ll rrr;     \
  8.   cin >> rrr; \
  9.   for (ll w1 = 0; w1 < rrr; w1++)
  10. #define cin(vec, a) for (ll i = 0; i < a && cin >> vec[i]; i++)
  11. #define cout(vec, a) for (ll i = 0; i < a && cout << vec[i] << " "; i++)
  12. #define MOD 1000000007
  13. #define PI 3.14159265
  14. #define ceil(a, b) ((a / b) + (a % b ? 1 : 0))
  15. #define all(v) v.begin(), v.end()
  16. #define rall(v) v.rbegin(), v.rend()
  17. #include <iostream>
  18. #define INF 1e9
  19. #define mod 1000000007
  20. #include <string>
  21. #define el '\n'
  22. #define sp ' '
  23. #define loop(n) for (int i = 0; i < n; i++)
  24. typedef long long ll;
  25. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  26. #define multi_ordered_set tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
  27.  
  28. void sasa()
  29. {
  30.   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  31. #ifndef ONLINE_JUDGE
  32.   freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  33. #endif
  34. }
  35.  
  36. struct s
  37. {
  38.   bool operator()(pair<ll,ll> a,pair<ll,ll> b)
  39.   {
  40.     if(a.first == b.first)
  41.       return a.second < b.second;
  42.     return a.first < b.first;
  43.   }
  44. };
  45. void solve()
  46. {
  47.     ll n,m;
  48.     int res1=0,res2=0;
  49.     cin >> n >> m ;
  50.     vector<pair<ll,ll>> a,b;
  51.     map<pair<ll,ll>,ll> mp1,mp2;
  52.     for(int i = 0 ; i < n ; i++)
  53.     {
  54.       int l,k;
  55.       cin >> l >> k;
  56.       mp1[{k,l}]++;
  57.     }
  58.     for(int i = 0 ; i < m ; i++)
  59.     {
  60.       int l,k;
  61.       cin >> l >> k;
  62.       mp2[{k,l}]++;
  63.     }
  64.     for(auto& i : mp1)
  65.     {
  66.  
  67.         if(mp2[i.first] !=0)
  68.         {
  69.             res1+=min(i.second,mp2[i.first]);
  70.             res2+=min(i.second,mp2[i.first]);
  71.             int k = min(i.second,mp2[i.first]);
  72.             i.second -= k;
  73.             mp2[i.first] -= k;
  74.         }
  75.  
  76.     }
  77.  
  78.     for(auto& i : mp1)
  79.     {
  80.         if(i.second != 0)
  81.         {
  82.             a.push_back(i.first);
  83.         }
  84.     }
  85.     for(auto& i : mp2)
  86.     {
  87.         if(i.second != 0)
  88.         {
  89.            
  90.             b.push_back(i.first);
  91.         }
  92.     }
  93.  
  94.     sort(all(a),s());
  95.     sort(all(b),s());
  96.     int i=0,j=0;
  97.  
  98.     while(i < a.size() && j < b.size())
  99.     {
  100.         if(a[i].first == b[j].first && a[i].second == b[j].second)
  101.         {
  102.             i++;
  103.             j++;
  104.             res1++;
  105.             res2++;
  106.         }
  107.         else if (a[i].first == b[j].first)
  108.         {
  109.             i++;
  110.             j++;
  111.             res1++;
  112.         }
  113.         else if (a[i].first < b[j].first)
  114.         {
  115.             i++;
  116.         }
  117.         else
  118.         {
  119.             j++;
  120.         }
  121.        
  122.     }
  123.     cout << res1 << " " << res2 << el;
  124. }
  125.  
  126. int main()
  127. {
  128.   sasa();
  129.  
  130.   ll t = 1, i = 1;
  131.   // cin >> t;
  132.   while (t--)
  133.   {
  134.     //  cout << "Case #" << i << ": ";
  135.     solve();
  136.     i++;
  137.     if (!t)
  138.       break;
  139.     cout << "\n";
  140.   }
  141.  
  142.   return 0;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement