Cod sursa(job #2528474)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 21 ianuarie 2020 22:27:30
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#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;
}