Cod sursa(job #1821896)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 3 decembrie 2016 20:47:24
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define x first
#define y second
const int MAX = 16000;

typedef pair<int, int> points;

points v[MAX + 1];
int n, m;
vector<int> aint[1 << 15];

void join(int node)
{
    int st = node * 2;
    int dr = node * 2 + 1;
    int i = 0, j = 0;
    while(i < aint[st].size() && j < aint[dr].size())
    {
        if(aint[st][i] <= aint[dr][j])
            aint[node].push_back(aint[st][i++]);
        else if(aint[st][i] > aint[dr][j])
            aint[node].push_back(aint[dr][j++]);
    }

    while(i < aint[st].size())
        aint[node].push_back(aint[st][i++]);
    while(j < aint[dr].size())
        aint[node].push_back(aint[dr][j++]);
}

void build_aint(int node, int left, int right)
{
    if(left == right)
    {
        aint[node].push_back(v[left].y);
        return;
    }
    int mid = (left + right) / 2;
    build_aint(2 * node, left, mid);
    build_aint(2 * node + 1, mid + 1, right);
    join(node);
}

int query(int node, int left, int right, int x1, int y1, int x2, int y2)
{
    int mid = (left + right) / 2, st ,dr;
    int sol = 0;

    if(x1 <= v[left].x && v[right].x <= x2)
    {
        st = lower_bound(aint[node].begin(), aint[node].end(), y1) - aint[node].begin();
        dr = upper_bound(aint[node].begin(), aint[node].end(), y2) - aint[node].begin();
        return dr - st;
    }

    if(left == right)
        return 0;
    if(x1 <= v[mid].x)
        sol += query(2 * node, left, mid, x1, y1, x2, y2);
    if(v[mid + 1].x <= x2)
        sol += query(2 * node + 1, mid + 1, right, x1, y1, x2, y2);

    return sol;
}


int main()
{
    FILE *fin, *fout;

    fin = fopen("zoo.in", "r");
    fout = fopen("zoo.out", "w");

    fscanf(fin, "%d", &n);

    for(int i = 1; i <= n; i++)
        fscanf(fin, "%d%d", &v[i].x, &v[i].y);

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

    build_aint(1, 1, n);

    fscanf(fin, "%d", &m);

    for(int i = 1; i <= m; i++)
    {
        int x1, y1, x2, y2;
        fscanf(fin, "%d%d%d%d", &x1, &y1, &x2, &y2);
        fprintf(fout, "%d\n", query(1, 1, n, x1, y1, x2, y2));
    }

    return 0;
}