Cod sursa(job #2293712)

Utilizator FrequeAlex Iordachescu Freque Data 1 decembrie 2018 14:43:01
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 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 fi first
#define se 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;

    Point()
    {
        x = y = 0;
    }

    Point(int _x, int _y)
    {
        x = _x;
        y = _y;
    }

    bool operator <(const Point &arg) const
    {
        if (y == arg.y)
            return x < arg.x;
        return y < arg.y;
    }
};

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;
}