Advertisement
konchin_shih

a524: Holo Coordinate System

Jan 3rd, 2021
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.75 KB | None | 0 0
  1. //Input Output
  2. #include<iostream>
  3. #include<iomanip>
  4. #include<fstream>
  5. #include<sstream>
  6. #include<streambuf>
  7. //C lib
  8. #include<cstdlib>
  9. #include<cstring>
  10. #include<cmath>
  11. #include<climits>
  12. #include<cctype>
  13. //Container
  14. #include<array>
  15. #include<vector>
  16. #include<stack>
  17. #include<queue>
  18. #include<deque>
  19. #include<list>
  20. #include<bitset>
  21. #include<set>
  22. #include<map>
  23. #include<unordered_set>
  24. #include<unordered_map>
  25. //Others
  26. #include<tuple>
  27. #include<algorithm>
  28. #include<functional>
  29. #include<numeric>
  30. #include<iterator>
  31. #include<limits>
  32. #include<utility>
  33. #include<complex>
  34. #include<type_traits>
  35. #include<initializer_list>
  36. #include<random>
  37.  
  38. using namespace std;
  39.  
  40. #if __cplusplus > 201703L
  41. #include<concepts>
  42. #include<ranges>
  43. #include<bit>
  44. #include<numbers>
  45. using namespace numbers;
  46. #include<span>
  47. #endif
  48.  
  49. #define debug(x) cout << #x << " : " << x << '\n' << flush
  50.  
  51. namespace abb {
  52. using ll = long long;
  53. using uint = unsigned int;
  54. using ull = unsigned long long;
  55. template<typename T> using V = vector<T>;
  56. template<typename T> using Q = queue<T>;
  57. template<typename T> using DQ = deque<T>;
  58. template<typename T> using V2d = vector<vector<T>>;
  59. template<typename T> using US = unordered_set<T>;
  60. template<typename T, size_t s> using A = array<T, s>;
  61. template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
  62. template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
  63. template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
  64. template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
  65. template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
  66. template<typename T> using F = function<T>;
  67. }
  68.  
  69. namespace output {
  70. template<typename T1, typename T2>
  71. inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  72.     return os << '(' << p.first << ", " << p.second << ')';
  73. }
  74. #define unfold1(Container) \
  75. template<typename T> \
  76. inline ostream& operator<<(ostream& os, const Container<T>& x) { \
  77.     for (const auto& i : x) \
  78.         os << i << ' '; \
  79.     return os; \
  80. }
  81. #define unfold2(Container) \
  82. template<typename T1,typename T2> \
  83. inline ostream& operator<<(ostream& os,const Container<T1,T2>& x){ \
  84.     for (const auto& i : x) \
  85.         os << i << ' '; \
  86.     return os; \
  87. }
  88. unfold1(vector); unfold1(set); unfold1(deque); unfold2(map)
  89. #undef unfold1
  90. #undef unfold2
  91. };
  92.  
  93. namespace rit {
  94. struct fast_istream {
  95.     operator bool() const {return bool(cin);}
  96.     fast_istream() {cin.tie(nullptr);}
  97. } fin;
  98. #if __cplusplus > 201703L
  99. template<typename T>
  100. fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
  101. #else
  102. template<typename T, class = typename enable_if<is_integral<T>::value>::type>
  103. fast_istream & operator>>(fast_istream& is, T& n) {
  104. #endif
  105.     while (isspace(cin.rdbuf()->sgetc()))
  106.         cin.rdbuf()->snextc();
  107.     bool sign = false;
  108.     if (cin.rdbuf()->sgetc() == '-')
  109.         sign = true, cin.rdbuf()->snextc();
  110.     for (n = 0; isdigit(cin.rdbuf()->sgetc());)
  111.         n *= 10, n += cin.rdbuf()->sbumpc() - '0';
  112.     n = sign ? -n : n;
  113.     return is;
  114. }
  115. fast_istream& operator>>(fast_istream& is, char& n) {
  116.     while (isspace(cin.rdbuf()->sgetc()))
  117.         cin.rdbuf()->snextc();
  118.     n = cin.rdbuf()->sbumpc();
  119.     return is;
  120. }
  121. }
  122.  
  123. #define endl '\n'
  124. namespace wit {
  125. struct fast_ostream {
  126.     operator bool() const {return bool(cout);}
  127.     fast_ostream() {cout.tie(nullptr);}
  128. } fout;
  129. constexpr int buffer_size = 30;
  130. #if __cplusplus > 201703L
  131. template<typename T>
  132. fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
  133. #else
  134. template<typename T, class = typename enable_if<is_integral<T>::value>::type>
  135. fast_ostream & operator<<(fast_ostream& os, T n) {
  136. #endif
  137.     if (!n) {cout.rdbuf()->sputc('0'); return os;}
  138.     if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
  139.     static char buffer[buffer_size];
  140.     int cnt = buffer_size;
  141.     for (; n; n /= 10)
  142.         buffer[--cnt] = n % 10 + '0';
  143.     cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
  144.     return os;
  145. }
  146. fast_ostream& operator<< (fast_ostream& os, const char& n) {
  147.     cout.rdbuf()->sputc(n); return os;
  148. }
  149. }
  150.  
  151. namespace algo {
  152. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  153. inline void sort(T& v, function<bool(Val, Val)> cmp = less <Val>()) {sort(v.begin(), v.end(), cmp);}
  154. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  155. inline _ lower_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return lower_bound(v.begin(), v.end(), x, cmp);}
  156. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  157. inline _ upper_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return upper_bound(v.begin(), v.end(), x, cmp);}
  158. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  159. inline void iota(T& v, const Val& x) {iota(v.begin(), v.end(), x);}
  160. }
  161.  
  162. //sublime autofill keywords:
  163. /*STL: push_back emplace_back pop_back push pop push_front pop_front size assign resize empty*/
  164. /*algorithm: lower_bound upper_bound equal_range next_permutation prev_permutation binary_search*/
  165. /*copy replace for_each fill find unique remove is_sorted min max min_element max_element*/
  166. /*ios: fixed setprecision setw stringstream / numeric: iota accumulate adjacent_difference partial_sum*/
  167. /*utility: move / limits: numeric_limits / iterator: begin end back_inserter front_inserter distance next prev*/
  168.  
  169. //#define MULTI_TASKCASE
  170. using namespace abb;
  171. using namespace output;
  172. using namespace rit;
  173. using namespace wit;
  174. using namespace algo;
  175.  
  176. inline void init() {
  177.  
  178. }
  179.  
  180. struct xnode {
  181.     int v;
  182.     xnode *l, *r;
  183.     xnode(): v(0) {l = r = nullptr;}
  184. };
  185. struct ynode {
  186.     int v;
  187.     ynode *l, *r;
  188.     xnode *data;
  189.     ynode(): v(0) {l = r = nullptr; data = nullptr;}
  190. }*root = nullptr;
  191.  
  192. #define m ((l + r) >> 1)
  193. using xstree = xnode*;
  194. using ystree = ynode*;
  195. constexpr int mxl = -1e8, mxr = 1e8, myl = -1e8, myr = 1e8;
  196.  
  197. void xincrease(int x, xstree& cur, int l = mxl, int r = mxr) {
  198.     if (x < l || r < x) return;
  199.     if (!cur) cur = new xnode;
  200.     if (l == r) {cur->v++; return;}
  201.     xincrease(x, cur->l, l, m);
  202.     xincrease(x, cur->r, m + 1, r);
  203.     cur->v = (cur->l ? cur->l->v : 0) + (cur->r ? cur->r->v : 0);
  204. }
  205.  
  206. void yincrease(int x, int y, ystree& cur, int l = myl, int r = myr) {
  207.     if (y < l || r < y) return;
  208.     if (!cur) cur = new ynode;
  209.     xincrease(x, cur->data); if (l == r) return;
  210.     yincrease(x, y, cur->l, l, m);
  211.     yincrease(x, y, cur->r, m + 1, r);
  212. }
  213.  
  214. inline void increase(int x, int y) {
  215.     yincrease(x, y, root);
  216. }
  217.  
  218. int xquery(int qxl, int qxr, xstree cur, int l = mxl, int r = mxr) {
  219.     if (qxr < l || r < qxl || !cur) return 0;
  220.     if (qxl <= l && r <= qxr) return cur->v;
  221.     return xquery(qxl, qxr, cur->l, l, m) +
  222.            xquery(qxl, qxr, cur->r, m + 1, r);
  223. }
  224.  
  225. int yquery(int qxl, int qxr, int qyl, int qyr, ystree cur, int l = myl, int r = myr) {
  226.     if (qyr < l || r < qyl || !cur) return 0;
  227.     if (qyl <= l && r <= qyr) return xquery(qxl, qxr, cur->data);
  228.     return yquery(qxl, qxr, qyl, qyr, cur->l, l, m) +
  229.            yquery(qxl, qxr, qyl, qyr, cur->r, m + 1, r);
  230. }
  231.  
  232. inline int query(int qxl, int qxr, int qyl, int qyr) {
  233.     return yquery(qxl, qxr, qyl, qyr, root);
  234. }
  235.  
  236. #undef m
  237.  
  238. inline void solve() {
  239.     int n, q, x, y;
  240.     cin >> n >> q;
  241.     while (n--)
  242.         cin >> x >> y, increase(x, y);
  243.     int qx1, qy1, qx2, qy2;
  244.     while (q--) {
  245.         cin >> qx1 >> qy1 >> qx2 >> qy2;
  246.         cout << query(qx1, qx2, qy1, qy2) << endl;
  247.     }
  248. }
  249.  
  250. //#define FILEIO
  251. main() {
  252.     ios::sync_with_stdio(false);
  253. #ifdef FILEIO
  254.     fstream filein("in.txt", ios::in);
  255.     fstream fileout("out.txt", ios::out);
  256.     cin.rdbuf(filein.rdbuf());
  257.     cout.rdbuf(fileout.rdbuf());
  258. #endif
  259.     init();
  260.     int t = 1;
  261. #ifdef MULTI_TASKCASE
  262.     cin >> t; cin.ignore();
  263. #endif
  264.     while (t--) solve();
  265.     return 0;
  266. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement