Cod sursa(job #2340060)

Utilizator AlexiaAndreea16Alexia Paunescu AlexiaAndreea16 Data 9 februarie 2019 18:43:35
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <bits/stdc++.h>

#define ios ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define enter cout << '\n'



using namespace std;



typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef vector <int> vi;

typedef vector <pii> vii;

typedef vector <ll> vl;

typedef vector <pll> vll;

typedef queue <int> qi;

typedef queue <pii> qii;

typedef queue <ll> ql;

typedef queue <pll> qll;



const int INF = SHRT_MAX - 2;

const int MOD = 100019;

const int EPSILON = 0.0000000001;

const short NMAX = 16000 + 5;



ifstream fin("zoo.in");

ofstream fout("zoo.out");

/*
{1}
struct Point
{1}
{
{1}
    int x, y;
{1}
{1}
{1}
    Point()
{1}
    {
{1}
        x = y = 0;
{1}
    }
{1}
{1}
{1}
    Point(int _x, int _y)
{1}
    {
{1}
        x = _x;
{1}
        y = _y;
{1}
    }
{1}
{1}
{1}
    bool operator <(const Point &arg) const
{1}
    {
{1}
        if (x == arg.x)
{1}
            return y < arg.y;
{1}
        return x < arg.x;
{1}
    }
{1}
};
{1}
*/



typedef pair<int, int> Point;



vi aint[5 * NMAX];

int n, m;

Point v[NMAX];



void build(int node, int st, int dr)

{

    for (int i = st; i <= dr; ++i)

        aint[node].pb(v[i].y);

    sort(aint[node].begin(), aint[node].end());



    if (st >= dr) return;



    int mijl = (st + dr) / 2;

    build(2 * node, st, mijl);

    build(2 * node + 1, mijl + 1, dr);

}



int query(int node, int st, int dr, int left, int right, int y1, int y2)

{

    if (left <= st && dr <= right)

        return upper_bound(aint[node].begin(), aint[node].end(), y2) - lower_bound(aint[node].begin(), aint[node].end(), y1);



    int ans = 0, mijl = (st + dr) / 2;

    if (left <= mijl) ans += query(2 * node, st, mijl, left, right, y1, y2);

    if (mijl < right) ans += query(2 * node + 1, mijl + 1, dr, left, right, y1, y2);



    return ans;

}



void write()

{

    int x1, x2, y1, y2, left, right;



    fin >> m;

    for (int i = 1; i <= m; ++i)

    {

        fin >> x1 >> y1 >> x2 >> y2;



        left = lower_bound(v + 1, v + n + 1, Point(x1, y1)) - v;

        right = upper_bound(v + 1, v + n + 1, Point(x2, y2)) - v - 1;



        if (left > right) fout << "0\n";

        else fout << query(1, 1, n, left, right, y1, y2) << '\n';

    }

}



void read()

{

    fin >> n;

    for (int i = 1; i <= n; ++i)

        fin >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1);

}



int main()

{

    read();

    build(1, 1, n);

    write();



    return 0;

}