Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define _USE_MATH_DEFINES
- #include <bits/stdc++.h>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld; // GCC - long double, but VS - double
- template<typename T> using vv = vector<vector<T>>;
- template<typename T> using pp = pair<T, T>;
- #define fr(i, n) for(int i = 0; i < n; ++i)
- #define rep(i, a, b) for(int i = a; i <= b; ++i)
- #define all(a) a.begin(), a.end()
- #define rall(a) a.rbegin(), a.rend()
- #define pb push_back
- #define nl '\n'
- #define file(name1, name2) freopen(name1, "r", stdin); freopen(name2, "w", stdout);
- #define zp_v(v) for(int i = 0; i < v.size(); ++i) cin >> v[i]
- #define zp_vv(v) fr(i, v.size())fr(j, v[i].size()) cin >> v[i][j];
- #define print_v(v) for (auto& u : v){ cout << u << ' '; }
- #define print_vv(v) for (auto& u : v){ for (auto& q : u) cout << q << ' '; cout << nl;}
- //const int N = 2e9 + 1;
- const int N = 10;
- struct stroka //y
- {
- int left, right, sum;
- stroka* child_left, * child_right;
- stroka(int l = -N, int r = N, int sum_ = 0)
- {
- left = l;
- right = r;
- sum = sum_;
- child_left = child_right = 0;
- }
- };
- struct stolb // x
- {
- int left, right;
- stolb* child_left, * child_right;
- stroka* str;
- stolb(int l = -N, int r = N)
- {
- left = l;
- right = r;
- child_left = child_right = 0;
- str = new stroka();
- }
- };
- stroka* new_stroka(int l, int r)
- {
- stroka* add = new stroka(l, r, 0);
- return add;
- }
- stolb* new_stolb(int l, int r)
- {
- stolb* add = new stolb(l, r);
- return add;
- }
- void update_str(stroka* root, const int& y)
- {
- if (root->left > y || root->right < y)
- return;
- if (root->left == root->right)
- {
- root->sum++;
- return;
- }
- int mid = root->left + root->right >> 1;
- if (root->child_left == 0)
- root->child_left = new_stroka(root->left, mid);
- if (root->child_right == 0)
- root->child_right = new_stroka(mid + 1, root->right);
- update_str(root->child_left, y);
- update_str(root->child_right, y);
- root->sum = root->child_left->sum + root->child_right->sum;
- }
- void update_sto(stolb* root, const int& x, const int& y)
- {
- if (root->left > x || root->right < x)
- return;
- if (root->left == root->right)
- {
- update_str(root->str, y);
- return;
- }
- int mid = root->left + root->right >> 1;
- if (root->child_left == 0)
- root->child_left = new_stolb(root->left, mid);
- if (root->child_right == 0)
- root->child_right = new_stolb(mid + 1, root->right);
- update_sto(root->child_left, x, y);
- update_sto(root->child_right, x, y);
- }
- int query_str(stroka* root, const int& y, const int& y1)
- {
- if (root == 0)
- return 0;
- if (root->left > y1 || root->right < y)
- return 0;
- if (root->left >= y && root->right <= y1)
- return root->sum;
- return query_str(root->child_left, y, y1) + query_str(root->child_right, y, y1);
- }
- int query_st(stolb* root, const int& x, const int& y, const int& x1, const int& y1)
- {
- if (root == 0)
- return 0;
- if (root->left > x1 || root->right < x)
- return 0;
- if (root->left >= x && root->right <= x1)
- return query_str(root->str, y, y1);
- return query_st(root->child_left, x, y, x1, y1) + query_st(root->child_right, x, y, x1, y1);
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- stolb* root = new stolb(-N, N);
- fr(i, n)
- {
- int x, y;
- cin >> x >> y;
- /*if (x == 1 and y == -1)
- cout << 'r' << nl;*/
- update_sto(root, x, y);
- }
- int m;
- cin >> m;
- fr(i, m)
- {
- int x, y, x1, y1;
- cin >> x >> y >> x1 >> y1;
- cout << query_st(root, x, y, x1, y1) << nl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement