Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #include <cstring>
- #define task "ADWINS"
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 2e5 + 2;
- int n;
- struct BIT
- {
- int a[N * 2];
- int n;
- void clear()
- {
- memset(a, 0, sizeof a);
- n = 0;
- }
- BIT()
- {
- memset(a, 0, sizeof a);
- n = 0;
- }
- void Update(int p, int v)
- {
- for (; p <= n; p += p & -p)
- a[p] += v;
- }
- int Sum(int p)
- {
- int ans = 0;
- for (; p > 0; p -= p & -p)
- ans += a[p];
- return ans;
- }
- int Get(int a, int b)
- {
- return Sum(b) - Sum(a - 1);
- }
- } x, y;
- struct Rec
- {
- int x, y, z, t;
- } a[N];
- vector<int> sx, cx, in[N * 2], out[N * 2];
- template <class T>
- void Unique(vector<T> &s)
- {
- sort(s.begin(), s.end());
- s.resize(unique(s.begin(), s.end()) - s.begin());
- }
- template <class T>
- int Find(vector<T> &s, T &a)
- {
- return lower_bound(s.begin(), s.end(), a) - s.begin();
- }
- void Read()
- {
- cin >> n;
- for (int i = 1; i <= n; ++i)
- {
- cin >> a[i].x >> a[i].y >> a[i].z >> a[i].t;
- sx.push_back(a[i].x);
- sx.push_back(a[i].z);
- cx.push_back(a[i].y);
- cx.push_back(a[i].t);
- }
- Unique(sx);
- Unique(cx);
- }
- void Solve()
- {
- for (int i = 1; i <= n; ++i)
- {
- in[Find(sx, a[i].x) + 1].push_back(i);
- out[Find(sx, a[i].z) + 1].push_back(i);
- }
- ll ans = 0;
- x.n = y.n = cx.size();
- for (int i = 1; i <= sx.size(); ++i)
- {
- //cout << i << ":\n";
- for (auto j : in[i])
- {
- int t = Find(cx, a[j].y) + 1,
- h = Find(cx, a[j].t) + 1;
- ans += x.Get(1, h) - y.Get(1, t - 1);
- x.Update(t, 1);
- y.Update(h, 1);
- }
- for (auto j : out[i])
- {
- x.Update(Find(cx, a[j].y) + 1, -1);
- y.Update(Find(cx, a[j].t) + 1, -1);
- //cout << "*";
- }
- //cout << x.Sum(x.n) << " " << y.Sum(y.n) << "\n";
- //cout << "ans is: " << ans << "\n";
- }
- cout << ans << "\n";
- }
- void Destroy()
- {
- for (int i = 1; i <= sx.size(); ++i)
- {
- in[i].clear();
- out[i].clear();
- }
- sx.clear();
- cx.clear();
- x.clear();
- y.clear();
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- int t;
- for (cin >> t; t--;)
- {
- Read();
- Solve();
- Destroy();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement