CF1190D Tokitsukaze and Strange Rectangle

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 200005;
 5 int n, x[N], y[N], bit[N];
 6 vector<int> v[N];
 7 void compress(vector<int>& x)
 8 {
 9     sort(x.begin(), x.end());
10     x.erase(unique(x.begin(), x.end()), x.end());
11 }
12 int lowbit(int x) { return x & -x; }
13 void add(int i, int x)
14 {
15     while (i <= n) { bit[i] += x; i += lowbit(i); }
16 }
17 int sum(int i)
18 {
19     int ans = 0;
20     while (i) { ans += bit[i]; i -= lowbit(i); }
21     return ans;
22 }
23 int main()
24 {
25     while (cin >> n)
26     {
27         memset(bit, 0, sizeof bit);
28         for (int i = 1; i <= n; i++) v[i].clear();
29         vector<int> vx, vy;
30         for (int i = 1; i <= n; i++)
31         {
32             cin >> x[i] >> y[i];
33             vx.push_back(x[i]); vy.push_back(y[i]);
34         }
35         compress(vx); compress(vy);
36         for (int i = 1; i <= n; i++)
37         {
38             x[i] = lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin() + 1;
39             y[i] = lower_bound(vy.begin(), vy.end(), y[i]) - vy.begin() + 1;
40             v[y[i]].push_back(x[i]);
41         }
42         ll ans = 0;
43         for (int i = n; i >= 1; i--)
44         {
45             sort(v[i].begin(), v[i].end());
46             for (int j = 0; j < v[i].size(); j++)
47             {
48                 int t = v[i][j];
49                 if (sum(t) - sum(t - 1)) continue;
50                 add(t, 1);
51             }
52             int prev = 0;
53             for (int j = 0; j < v[i].size(); j++)
54             {
55                 int t = v[i][j];
56                 ans += 1ll * (sum(t - 1) - sum(prev) + 1) * (sum(n) - sum(t) + 1);
57                 prev = t;
58             }
59         }
60         cout << ans << endl;
61     }
62     return 0;
63 }