Cod sursa(job #1572522)

Utilizator claudiuarseneClaudiu Arsene claudiuarsene Data 18 ianuarie 2016 22:52:25
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>
#define maxN 16002
#define maxM 100002
#define f first
#define pb push_back
#define s second
using namespace std;
pair < int, int > V[maxN];
vector < int > arb[maxN * 4 * 4], cx;
int n, m, p, q, sol, ay, by;
void update(int node, int l, int r)
{
    if (l == r)
    {
        arb[node].pb(V[r].s);
        return;
    }
    int mid = (l + r) >> 1, lson = 2 * node, rson = lson + 1;
    //if (l <= mid)
        update(lson, l, mid);
    //if (r > mid)
        update(rson, mid + 1, r);
    arb[node].resize(arb[lson].size() + arb[rson].size());
    merge(arb[lson].begin(), arb[lson].end(), arb[rson].begin(), arb[rson].end(), arb[node].begin());
}
void query(int node, int l, int r)
{
    int left, right;
    if (p <= l && q >= r)
    {
        left = lower_bound(arb[node].begin(), arb[node].end(), ay) - arb[node].begin();
        right = upper_bound(arb[node].begin(), arb[node].end(), by)- arb[node].begin();
        sol += right - left;
        return ;
    }
    if (l != r)
    {
        int mid = (l + r) >> 1, lson = 2 * node, rson = lson + 1;
        if (p <= mid)
        query(lson, l, mid);
        if (q > mid)
        query(rson, mid + 1, r);
    }
}
void read()
{
    int i;
    freopen("zoo.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &V[i].f, &V[i].s);
        cx.pb(V[i].f);
    }
}
void solve()
{
   sort(cx.begin(), cx.end());
    sort(V + 1, V + n + 1);
    update(1, 1, n);
}
void write()
{
    int ax, bx;
    freopen("zoo.out", "w", stdout);
    scanf("%d", &m);
    while (m --)
    {
        scanf("%d %d %d %d", &ax, &ay, &bx, &by);
        p = lower_bound(cx.begin(), cx.end(), ax) - cx.begin() + 1;
        q = upper_bound(cx.begin(), cx.end(), bx) - cx.begin();
        query(1, 1, n);
        printf("%d\n", sol);
        sol = 0;
    }
}
int main()
{
    read();
     solve();
    write();
    return 0;
}