Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5. #define Nmax 16005
  6.  
  7. using namespace std;
  8.  
  9. ifstream f("zoo.in");
  10. ofstream g("zoo.out");
  11.  
  12. int n;
  13. int q, x1, y1, x2, y2;
  14. vector <int> arbint[4*Nmax];
  15. pair <int, int> v[Nmax];
  16.  
  17. void read()
  18. {
  19.     f >> n;
  20.     for (int i = 1, x, y; i <= n; i++)
  21.     {
  22.         f >> x >> y;
  23.         v[i]={x, y};
  24.     }
  25. }
  26.  
  27. void build(int st, int dr, int nod)
  28. {
  29.     for (int i = st; i <= dr; i++) arbint[nod].push_back(v[i].second);
  30.     sort (arbint[nod].begin(), arbint[nod].end());
  31.  
  32.     if (st == dr) return;
  33.  
  34.     int md=(st+dr)/2;
  35.     build (st, md, 2*nod);
  36.     build (md+1, dr, 2*nod+1);
  37.  
  38. }
  39.  
  40. int query(int nod, int st, int dr, int st_q, int dr_q)
  41. {
  42.     int ans=0;
  43.  
  44.     if (st >= st_q && dr_q >= dr) return upper_bound(arbint[nod].begin(), arbint[nod].end(), y2)-
  45.                                          lower_bound(arbint[nod].begin(), arbint[nod].end(), y1);
  46.  
  47.     int md=(st+dr)/2;
  48.     if (md >= st_q) ans += query (2*nod, st, md, st_q, dr_q);
  49.     if (md < dr_q) ans += query (2*nod+1, md+1, dr, st_q, dr_q);
  50.     return  ans;
  51. }
  52.  
  53. int bs_lo(int x)
  54. {
  55.     int st = 1, dr = n;
  56.     int ans=-1;
  57.     while (st <= dr)
  58.     {
  59.         int mid = (st+dr)/2;
  60.         if(v[mid].first>=x) dr=mid;
  61.         else st = mid+1;
  62.     }
  63.     return ans;
  64. }
  65.  
  66. int bs_up( int x)
  67. {
  68.     int st = 0, dr = n;
  69.     int ans=-1;
  70.     while (st<=dr)
  71.     {
  72.         int mid = (st+dr)/2;
  73.         if(v[mid].first<=x) st=mid+1;
  74.         else dr = mid;
  75.     }
  76.     return ans;
  77. }
  78.  
  79. int main()
  80. {
  81.     read();
  82.     sort (v+1, v+n+1);
  83.     build(1, n, 1);
  84.  
  85.     f >> q;
  86.  
  87.     while (q--)
  88.     {
  89.         f >> x1 >> y1 >> x2 >> y2;
  90.         int stg=lower_bound(v+1, v+n+1, make_pair(x1, y1))-v;
  91.         int drp=upper_bound(v+1, v+n+1, make_pair(x2, y2))-v;
  92.         drp--;
  93.         // cout << '\n';
  94.         // cout << stg << " " << drp << '\n';
  95.         g << query (1, 1, n, stg, drp) << '\n';
  96.     }
  97.  
  98.  
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement