Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- #define Nmax 16005
- using namespace std;
- ifstream f("zoo.in");
- ofstream g("zoo.out");
- int n;
- int q, x1, y1, x2, y2;
- vector <int> arbint[4*Nmax];
- pair <int, int> v[Nmax];
- void read()
- {
- f >> n;
- for (int i = 1, x, y; i <= n; i++)
- {
- f >> x >> y;
- v[i]={x, y};
- }
- }
- void build(int st, int dr, int nod)
- {
- for (int i = st; i <= dr; i++) arbint[nod].push_back(v[i].second);
- sort (arbint[nod].begin(), arbint[nod].end());
- if (st == dr) return;
- int md=(st+dr)/2;
- build (st, md, 2*nod);
- build (md+1, dr, 2*nod+1);
- }
- int query(int nod, int st, int dr, int st_q, int dr_q)
- {
- int ans=0;
- if (st >= st_q && dr_q >= dr) return upper_bound(arbint[nod].begin(), arbint[nod].end(), y2)-
- lower_bound(arbint[nod].begin(), arbint[nod].end(), y1);
- int md=(st+dr)/2;
- if (md >= st_q) ans += query (2*nod, st, md, st_q, dr_q);
- if (md < dr_q) ans += query (2*nod+1, md+1, dr, st_q, dr_q);
- return ans;
- }
- int bs_lo(int x)
- {
- int st = 1, dr = n;
- int ans=-1;
- while (st <= dr)
- {
- int mid = (st+dr)/2;
- if(v[mid].first>=x) dr=mid;
- else st = mid+1;
- }
- return ans;
- }
- int bs_up( int x)
- {
- int st = 0, dr = n;
- int ans=-1;
- while (st<=dr)
- {
- int mid = (st+dr)/2;
- if(v[mid].first<=x) st=mid+1;
- else dr = mid;
- }
- return ans;
- }
- int main()
- {
- read();
- sort (v+1, v+n+1);
- build(1, n, 1);
- f >> q;
- while (q--)
- {
- f >> x1 >> y1 >> x2 >> y2;
- int stg=lower_bound(v+1, v+n+1, make_pair(x1, y1))-v;
- int drp=upper_bound(v+1, v+n+1, make_pair(x2, y2))-v;
- drp--;
- // cout << '\n';
- // cout << stg << " " << drp << '\n';
- g << query (1, 1, n, stg, drp) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement