Cod sursa(job #1487988)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 17 septembrie 2015 19:12:01
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 16000;

struct point
{
    int x, y;
} v[MAX_N];

vector <int> tree[2 * MAX_N];

bool cmp(const point &a, const point &b)
{
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

inline int query(int l, const int &y, int r, const int &Y)
{
    int ans = 0;

    while (l < r)
    {
        if (l & 1)
        {
            ans += upper_bound(tree[l].begin(), tree[l].end(), Y) - lower_bound(tree[l].begin(), tree[l].end(), y);
            l++;
        }
        if (r & 1)
        {
            r--;
            ans += upper_bound(tree[r].begin(), tree[r].end(), Y) - lower_bound(tree[r].begin(), tree[r].end(), y);
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

int main()
{
    ifstream in("zoo.in");
    ofstream out("zoo.out");
    int n, q;
    int x, y, X, Y;
    int lo, hi, mid;

    in >> n;
    for (int i = 0; i < n; i++)
        in >> v[i].x >> v[i].y;

    sort(v, v + n, cmp);

    for (int i = 0; i < n; i++)
        tree[i + n].emplace_back(v[i].y);
    for (int i = n - 1; i; i--)
        merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), back_inserter(tree[i]));

    in >> q;
    while (q--)
    {
        in >> x >> y >> X >> Y;

        lo = -1;
        hi = n;

        while (hi - lo > 1)
        {
            mid = (lo + hi) >> 1;
            if (v[mid].x >= x)
                hi = mid;
            else
                lo = mid;
        }
        x = hi;

        lo = -1;
        hi = n;

        while (hi - lo > 1)
        {
            mid = (lo + hi) >> 1;
            if (v[mid].x <= X)
                lo = mid;
            else
                hi = mid;
        }
        X = lo + 1;

        out << query(x + n, y, X + n, Y) << '\n';
    }
    in.close();
    out.close();
    return 0;
}