Cod sursa(job #1239870)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 9 octombrie 2014 21:54:48
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<unordered_map>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define x first
#define y second

using namespace std;

const int nmax = 16005;

int n, i, q, X1, Y1, X2, Y2, sol, a, b, l, r, m;
pair<int, int> p[nmax];
vector<int> seg[4 * nmax];

void build(int node, int l, int r)
{
    if(l == r)
    {
        seg[node].pb(p[l].y);
        return;
    }

    int m = (l + r) / 2;
    int ls = 2 * node;
    int rs = 2 * node + 1;

    build(ls, l, m);
    build(rs, m + 1, r);

    seg[node].resize(seg[ls].size() + seg[rs].size());

    merge(seg[ls].begin(), seg[ls].end(), seg[rs].begin(), seg[rs].end(), seg[node].begin());
}

void query(int node, int l, int r)
{
    if(l >= X1 && r <= X2)
    {
        int L = lower_bound(seg[node].begin(), seg[node].end(), Y1) - seg[node].begin();
        int U = upper_bound(seg[node].begin(), seg[node].end(), Y2) - seg[node].begin();
        sol += U - L;
        return;
    }

    int m = (l + r) / 2;
    int ls = 2 * node;
    int rs = 2 * node + 1;

    if(X1 <= m)
        query(ls, l, m);
    if(X2 > m)
        query(rs, m + 1, r);
}

int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    scanf("%d", &n);

    for(i = 1; i <= n; i++)
        scanf("%d%d", &p[i].x, &p[i].y);

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

    build(1, 1, n);

    scanf("%d", &q);

    for(; q; q--)
    {
        scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);

        a = b = -1;

        l = 1;
        r = n;
        while(l <= r)
        {
            m = (l + r) / 2;
            if(p[m].x >= X1)
            {
                a = m;
                r = m - 1;
            }
            else
                l = m + 1;
        }

        l = 1;
        r = n;
        while(l <= r)
        {
            m = (l + r) / 2;
            if(p[m].x <= X2)
            {
                b = m;
                l = m + 1;
            }
            else
                r = m - 1;
        }

        X1 = a;
        X2 = b;

        sol = 0;
        if(X1 <= X2)
            query(1, 1, n);

        printf("%d\n", sol);
    }

    return 0;
}