Advertisement
Dang_Quan_10_Tin

ADWINS

Apr 19th, 2021
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cstring>
  6. #define task "ADWINS"
  7. using namespace std;
  8. using ll = long long;
  9. using ld = long double;
  10.  
  11. const int N = 2e5 + 2;
  12. int n;
  13. struct BIT
  14. {
  15.     int a[N * 2];
  16.     int n;
  17.     void clear()
  18.     {
  19.         memset(a, 0, sizeof a);
  20.         n = 0;
  21.     }
  22.     BIT()
  23.     {
  24.         memset(a, 0, sizeof a);
  25.         n = 0;
  26.     }
  27.     void Update(int p, int v)
  28.     {
  29.         for (; p <= n; p += p & -p)
  30.             a[p] += v;
  31.     }
  32.     int Sum(int p)
  33.     {
  34.         int ans = 0;
  35.         for (; p > 0; p -= p & -p)
  36.             ans += a[p];
  37.         return ans;
  38.     }
  39.     int Get(int a, int b)
  40.     {
  41.         return Sum(b) - Sum(a - 1);
  42.     }
  43. } x, y;
  44.  
  45. struct Rec
  46. {
  47.     int x, y, z, t;
  48. } a[N];
  49. vector<int> sx, cx, in[N * 2], out[N * 2];
  50.  
  51. template <class T>
  52. void Unique(vector<T> &s)
  53. {
  54.     sort(s.begin(), s.end());
  55.     s.resize(unique(s.begin(), s.end()) - s.begin());
  56. }
  57.  
  58. template <class T>
  59. int Find(vector<T> &s, T &a)
  60. {
  61.     return lower_bound(s.begin(), s.end(), a) - s.begin();
  62. }
  63.  
  64. void Read()
  65. {
  66.     cin >> n;
  67.     for (int i = 1; i <= n; ++i)
  68.     {
  69.         cin >> a[i].x >> a[i].y >> a[i].z >> a[i].t;
  70.         sx.push_back(a[i].x);
  71.         sx.push_back(a[i].z);
  72.         cx.push_back(a[i].y);
  73.         cx.push_back(a[i].t);
  74.     }
  75.     Unique(sx);
  76.     Unique(cx);
  77. }
  78.  
  79. void Solve()
  80. {
  81.     for (int i = 1; i <= n; ++i)
  82.     {
  83.         in[Find(sx, a[i].x) + 1].push_back(i);
  84.         out[Find(sx, a[i].z) + 1].push_back(i);
  85.     }
  86.     ll ans = 0;
  87.     x.n = y.n = cx.size();
  88.     for (int i = 1; i <= sx.size(); ++i)
  89.     {
  90.         //cout << i << ":\n";
  91.         for (auto j : in[i])
  92.         {
  93.             int t = Find(cx, a[j].y) + 1,
  94.                 h = Find(cx, a[j].t) + 1;
  95.             ans += x.Get(1, h) - y.Get(1, t - 1);
  96.             x.Update(t, 1);
  97.             y.Update(h, 1);
  98.         }
  99.         for (auto j : out[i])
  100.         {
  101.             x.Update(Find(cx, a[j].y) + 1, -1);
  102.             y.Update(Find(cx, a[j].t) + 1, -1);
  103.             //cout << "*";
  104.         }
  105.         //cout << x.Sum(x.n) << " " << y.Sum(y.n) << "\n";
  106.         //cout << "ans is: " << ans << "\n";
  107.     }
  108.     cout << ans << "\n";
  109. }
  110.  
  111. void Destroy()
  112. {
  113.     for (int i = 1; i <= sx.size(); ++i)
  114.     {
  115.         in[i].clear();
  116.         out[i].clear();
  117.     }
  118.     sx.clear();
  119.     cx.clear();
  120.     x.clear();
  121.     y.clear();
  122. }
  123.  
  124. int32_t main()
  125. {
  126.     ios_base::sync_with_stdio(0);
  127.     cin.tie(0);
  128.     cout.tie(0);
  129.     if (fopen(task ".INP", "r"))
  130.     {
  131.         freopen(task ".INP", "r", stdin);
  132.         freopen(task ".OUT", "w", stdout);
  133.     }
  134.     int t;
  135.     for (cin >> t; t--;)
  136.     {
  137.         Read();
  138.         Solve();
  139.         Destroy();
  140.     }
  141. }
  142.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement