Cod sursa(job #1487997)

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

using namespace std;

const int MAX_N = 16000;
const int BUFFSIZE = 1024;

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

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

vector <int> tree[2 * MAX_N];

char buff[BUFFSIZE];
int ptr = BUFFSIZE;

inline char getChr()
{
    if (ptr == BUFFSIZE)
    {
        fread(buff, 1, BUFFSIZE, stdin);
        ptr = 0;
    }
    return buff[ptr++];
}

inline int readInt()
{
    register int q = 0;
    bool sign = 0;
    char c;

    do
    {
        c = getChr();
        sign |= (c == '-');
    } while (!isdigit(c));
    do
    {
        q = (q << 1) + (q << 3) + (c - '0');
        c = getChr();
    } while (isdigit(c));
    return q ^ ((q ^ -q) & -sign);
}

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()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    int n, q;
    int x, y, X, Y;
    int lo, hi, mid;

    n = readInt();
    for (int i = 0; i < n; i++)
        v[i] = { readInt(), readInt() };
    sort(v, v + n);

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

    q = readInt();
    while (q--)
    {
        x = readInt();
        y = readInt();
        X = readInt();
        Y = readInt();

        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;

        printf("%d\n", query(x + n, y, X + n, Y));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}