Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.78 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define _USE_MATH_DEFINES
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef unsigned long long      ull;
  7. typedef long long               ll;
  8. typedef long double             ld; // GCC - long double, but VS - double
  9.  
  10. template<typename T> using vv   = vector<vector<T>>;
  11. template<typename T> using pp   = pair<T, T>;
  12.  
  13. #define fr(i, n)                for(int i = 0; i < n; ++i)
  14. #define rep(i, a, b)            for(int i = a; i <= b; ++i)
  15. #define all(a)                  a.begin(), a.end()
  16. #define rall(a)                 a.rbegin(), a.rend()
  17. #define pb                      push_back
  18. #define nl                      '\n'
  19. #define file(name1, name2)      freopen(name1, "r", stdin); freopen(name2, "w", stdout);
  20. #define zp_v(v)                 for(int i = 0; i < v.size(); ++i) cin >> v[i]
  21. #define zp_vv(v)                fr(i, v.size())fr(j, v[i].size()) cin >> v[i][j];
  22. #define print_v(v)              for (auto& u : v){ cout << u << ' '; }
  23. #define print_vv(v)             for (auto& u : v){ for (auto& q : u) cout << q << ' '; cout << nl;}
  24.  
  25. //const int N = 2e9 + 1;
  26. const int N = 10;
  27. struct stroka //y
  28. {
  29.     int left, right, sum;
  30.     stroka* child_left, * child_right;
  31.  
  32.     stroka(int l = -N, int r = N, int sum_ = 0)
  33.     {
  34.         left = l;
  35.         right = r;
  36.         sum = sum_;
  37.         child_left = child_right = 0;
  38.     }
  39. };
  40.  
  41. struct stolb // x
  42. {
  43.     int left, right;
  44.     stolb* child_left, * child_right;
  45.     stroka* str;
  46.  
  47.     stolb(int l = -N, int r = N)
  48.     {
  49.         left = l;
  50.         right = r;
  51.         child_left = child_right = 0;
  52.  
  53.         str = new stroka();
  54.     }
  55. };
  56.  
  57. stroka* new_stroka(int l, int r)
  58. {
  59.     stroka* add = new stroka(l, r, 0);
  60.     return add;
  61. }
  62.  
  63. stolb* new_stolb(int l, int r)
  64. {
  65.     stolb* add = new stolb(l, r);
  66.     return add;
  67. }
  68.  
  69. void update_str(stroka* root, const int& y)
  70. {
  71.     if (root->left > y || root->right < y)
  72.         return;
  73.  
  74.     if (root->left == root->right)
  75.     {
  76.         root->sum++;
  77.         return;
  78.     }
  79.  
  80.     int mid = root->left + root->right >> 1;
  81.  
  82.     if (root->child_left == 0)
  83.         root->child_left = new_stroka(root->left, mid);
  84.  
  85.     if (root->child_right == 0)
  86.         root->child_right = new_stroka(mid + 1, root->right);
  87.  
  88.     update_str(root->child_left, y);
  89.     update_str(root->child_right, y);
  90.  
  91.     root->sum = root->child_left->sum + root->child_right->sum;
  92. }
  93.  
  94. void update_sto(stolb* root, const int& x, const int& y)
  95. {
  96.     if (root->left > x || root->right < x)
  97.         return;
  98.  
  99.     if (root->left == root->right)
  100.     {
  101.         update_str(root->str, y);
  102.         return;
  103.     }
  104.  
  105.     int mid = root->left + root->right >> 1;
  106.    
  107.     if (root->child_left == 0)
  108.         root->child_left = new_stolb(root->left, mid);
  109.  
  110.     if (root->child_right == 0)
  111.         root->child_right = new_stolb(mid + 1, root->right);
  112.  
  113.     update_sto(root->child_left, x, y);
  114.     update_sto(root->child_right, x, y);
  115.    
  116. }
  117.  
  118. int query_str(stroka* root, const int& y, const int& y1)
  119. {
  120.     if (root == 0)
  121.         return 0;
  122.  
  123.     if (root->left > y1 || root->right < y)
  124.         return 0;
  125.  
  126.     if (root->left >= y && root->right <= y1)
  127.         return root->sum;
  128.  
  129.     return query_str(root->child_left, y, y1) + query_str(root->child_right, y, y1);
  130. }
  131.  
  132. int query_st(stolb* root, const int& x, const int& y, const int& x1, const int& y1)
  133. {
  134.     if (root == 0)
  135.         return 0;
  136.  
  137.     if (root->left > x1 || root->right < x)
  138.         return 0;
  139.  
  140.     if (root->left >= x && root->right <= x1)
  141.         return query_str(root->str, y, y1);
  142.  
  143.     return query_st(root->child_left, x, y, x1, y1) + query_st(root->child_right, x, y, x1, y1);
  144. }
  145.  
  146. signed main()
  147. {
  148.     ios_base::sync_with_stdio(false);
  149.     cin.tie(0);
  150.     cout.tie(0);
  151.    
  152.     int n;
  153.     cin >> n;
  154.  
  155.     stolb* root = new stolb(-N, N);
  156.  
  157.     fr(i, n)
  158.     {
  159.         int x, y;
  160.         cin >> x >> y;
  161.  
  162.         /*if (x == 1 and y == -1)
  163.             cout << 'r' << nl;*/
  164.  
  165.         update_sto(root, x, y);
  166.     }
  167.    
  168.     int m;
  169.     cin >> m;
  170.  
  171.     fr(i, m)
  172.     {
  173.         int x, y, x1, y1;
  174.         cin >> x >> y >> x1 >> y1;
  175.         cout << query_st(root, x, y, x1, y1) << nl;
  176.     }
  177.  
  178.     return 0;
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement