Cod sursa(job #1239865)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 9 octombrie 2014 21:46:19
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 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;
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(p[l].x >= X1 && p[r].x <= 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;
    }

    if(l == r)
        return;

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

    if(X1 <= p[m].x)
        query(ls, l, m);
    if(X2 > p[m].x)
        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);

        sol = 0;
        query(1, 1, n);

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

    return 0;
}