Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
- #define ff first
- #define ss second
- #define pb push_back
- #define all(a) a.begin(), a.end()
- #define dbg(x) cerr<<" "<<#x<<" "<<x<<endl
- typedef long long ll;
- using namespace std;
- unordered_map <int, int> mp;
- struct segTree {
- int sz = 1;
- vector <vector <int>> tree;
- segTree(vector <vector <int>> &coord) {
- int n = coord.size();
- while(sz < n) {
- sz <<= 1;
- }
- tree = vector <vector <int>>(sz * 2 - 1);
- build(0, 0, sz, coord);
- }
- void build(int x, int lx, int rx, vector <vector <int>> &coord) {
- if(rx - lx == 1) {
- if(lx < coord.size()) {
- tree[x] = coord[lx];
- sort(all(tree[x]));
- }
- return;
- }
- int m = (lx + rx) >> 1;
- build(2 * x + 1, lx, m, coord);
- build(2 * x + 2, m, rx, coord);
- tree[x].resize(tree[2 * x + 1].size() + tree[2 * x + 2].size());
- merge(all(tree[2 * x + 1]), all(tree[2 * x + 2]), tree[x].begin());
- }
- ll get(int x, int lx, int rx, int l, int r, int low, int high) {
- if(rx <= l || lx >= r) {
- return 0;
- }
- if(lx >= l && rx <= r) {
- auto small = lower_bound(all(tree[x]), low),
- big = upper_bound(all(tree[x]), high);
- ll d1 = distance(tree[x].begin(), small), d2 = distance(tree[x].begin(), big);
- return (d2 - d1);
- }
- int m = (lx + rx) >> 1;
- return get(2 * x + 1, lx, m, l, r, low, high) + get(2 * x + 2, m, rx, l, r, low, high);
- }
- ll get(int l, int r, int low, int high) {
- return get(0, 0, sz, l, r, low, high);
- }
- };
- int main() {
- FASTER();
- int n;
- cin >> n;
- vector <int> xs(n);
- vector <pair <int, int>> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i].ff >> v[i].ss;
- xs[i] = v[i].ff;
- }
- sort(all(xs));
- xs.resize(unique(all(xs)) - xs.begin());
- for(int i = 0; i < xs.size(); i++) {
- mp[xs[i]] = i;
- }
- vector <vector <int>> coord(xs.size() + 1);
- for(auto a : v) {
- int id = mp[a.ff];
- coord[id].pb(a.ss);
- }
- segTree st(coord);
- int m;
- cin >> m;
- for(int _ = 0; _ < m; _++) {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- auto id1 = lower_bound(all(xs), x1), id2 = upper_bound(all(xs), x2);
- int l = distance(xs.begin(), id1), r = distance(xs.begin(), id2);
- ll ans = st.get(l, r, y1, y2);
- cout << ans << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment