Cod sursa(job #2302459)

Utilizator rares9301Sarmasag Rares rares9301 Data 14 decembrie 2018 17:50:06
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 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");

/*

struct Point

{

    int x, y;

{1}

    Point()

    {

        x = y = 0;

    }

{1}

    Point(int _x, int _y)

    {

        x = _x;

        y = _y;

    }

{1}

    bool operator <(const Point &arg) const

    {

        if (x == arg.x)

            return y < arg.y;

        return x < arg.x;

    }

};

*/

 

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;

}