ohwhatalovelyday

Untitled

Oct 4th, 2021
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  4. #define ff first
  5. #define ss second
  6. #define pb push_back
  7. #define all(a) a.begin(), a.end()
  8. #define dbg(x) cerr<<" "<<#x<<" "<<x<<endl
  9.  
  10. typedef long long ll;
  11.  
  12. using namespace std;
  13.  
  14. unordered_map <int, int> mp;
  15.  
  16. struct segTree {
  17.     int sz = 1;
  18.     vector <vector <int>> tree;
  19.  
  20.     segTree(vector <vector <int>> &coord) {
  21.         int n = coord.size();
  22.         while(sz < n) {
  23.             sz <<= 1;
  24.         }
  25.         tree = vector <vector <int>>(sz * 2 - 1);
  26.         build(0, 0, sz, coord);
  27.     }
  28.  
  29.     void build(int x, int lx, int rx, vector <vector <int>> &coord) {
  30.         if(rx - lx == 1) {
  31.             if(lx < coord.size()) {
  32.                 tree[x] = coord[lx];
  33.                 sort(all(tree[x]));
  34.             }
  35.             return;
  36.         }
  37.         int m = (lx + rx) >> 1;
  38.         build(2 * x + 1, lx, m, coord);
  39.         build(2 * x + 2, m, rx, coord);
  40.         tree[x].resize(tree[2 * x + 1].size() + tree[2 * x + 2].size());
  41.         merge(all(tree[2 * x + 1]), all(tree[2 * x + 2]), tree[x].begin());
  42.     }
  43.  
  44.     ll get(int x, int lx, int rx, int l, int r, int low, int high) {
  45.         if(rx <= l || lx >= r) {
  46.             return 0;
  47.         }
  48.         if(lx >= l && rx <= r) {
  49.             auto small = lower_bound(all(tree[x]), low),
  50.                 big = upper_bound(all(tree[x]), high);
  51.             ll d1 = distance(tree[x].begin(), small), d2 = distance(tree[x].begin(), big);
  52.             return (d2 - d1);
  53.         }
  54.         int m = (lx + rx) >> 1;
  55.         return get(2 * x + 1, lx, m, l, r, low, high) + get(2 * x + 2, m, rx, l, r, low, high);
  56.     }
  57.  
  58.     ll get(int l, int r, int low, int high) {
  59.         return get(0, 0, sz, l, r, low, high);
  60.     }
  61. };
  62.  
  63. int main() {
  64.     FASTER();
  65.     int n;
  66.     cin >> n;
  67.     vector <int> xs(n);
  68.     vector <pair <int, int>> v(n);
  69.     for(int i = 0; i < n; i++) {
  70.         cin >> v[i].ff >> v[i].ss;
  71.         xs[i] = v[i].ff;
  72.     }
  73.     sort(all(xs));
  74.     xs.resize(unique(all(xs)) - xs.begin());
  75.     for(int i = 0; i < xs.size(); i++) {
  76.         mp[xs[i]] = i;
  77.     }
  78.     vector <vector <int>> coord(xs.size() + 1);
  79.  
  80.     for(auto a : v) {
  81.         int id = mp[a.ff];
  82.         coord[id].pb(a.ss);
  83.     }
  84.  
  85.     segTree st(coord);
  86.     int m;
  87.     cin >> m;
  88.     for(int _ = 0; _ < m; _++) {
  89.         int x1, y1, x2, y2;
  90.         cin >> x1 >> y1 >> x2 >> y2;
  91.         auto id1 = lower_bound(all(xs), x1), id2 = upper_bound(all(xs), x2);
  92.         int l = distance(xs.begin(), id1), r = distance(xs.begin(), id2);
  93.         ll ans = st.get(l, r, y1, y2);
  94.         cout << ans << '\n';
  95.     }
  96. }
  97.  
Advertisement
Add Comment
Please, Sign In to add comment