Advertisement
Guest User

Untitled

a guest
Jun 24th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. /**
  2.  * Sergey Kopeliovich (burunduk30@gmail.com)
  3.  */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  10. #define all(p) p.begin(), p.end()
  11.  
  12. int main() {
  13.     int n;
  14.     cin >> n;
  15.     vector<pair<int, int>> p(n);
  16.     forn(i, n)
  17.         cin >> p[i].first >> p[i].second;
  18.     sort(all(p));
  19.  
  20.     vector<int> t[2 * n]; // [n,2n)
  21.     forn(i, n)
  22.         t[i + n] = {p[i].second};
  23.     for (int i = n - 1; i > 0; i--) {
  24.         t[i].resize(t[i * 2].size() + t[i * 2 + 1].size());
  25.         merge(all(t[2 * i]), all(t[2 * i + 1]), t[i].begin());
  26.     }
  27.  
  28.     auto inner_get = [&](int i, int y1, int y2) {
  29.         return upper_bound(all(t[i]), y2) - lower_bound(all(t[i]), y1);
  30.     };
  31.     auto get = [&](int x1, int x2, int y1, int y2) {
  32.         int l = lower_bound(all(p), make_pair(x1, y1)) - p.begin();
  33.         int r = upper_bound(all(p), make_pair(x2, y2)) - p.begin() - 1;
  34.  
  35.         int sum = 0;
  36.         for (l += n, r += n; l <= r; l /= 2, r /= 2) {
  37.             if (l % 2 == 1) sum += inner_get(l++, y1, y2);
  38.             if (r % 2 == 0) sum += inner_get(r--, y1, y2);
  39.         }
  40.         return sum;
  41.     };
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement