Cod sursa(job #931712)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 28 martie 2013 14:09:18
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
#define DIM 10000

using namespace std;

char buff[DIM];
int poz = 0;

void get(int &numar)
{
    numar = 0;
    bool semn = 0;
    while (buff[poz] < '0' || buff[poz] > '9')
    {
        if(buff[poz] == '-') semn = 1;
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    }

    while ('0'<=buff[poz] && buff[poz]<='9')
    {
        numar = numar*10 + buff[poz] - '0';
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    }
    if(semn) numar = -numar;
}

struct Point
{
    int x, y;
};

Point P[17000];
vector<int>Arb[400010];
int i, p, x, y, n, m, a, b, sol, Xmax;

bool cmp(Point a, Point b)
{
    return a.x < b.x;
}


void Insert(int nod, int l, int r)
{
    if(l == r)
    {
        Arb[nod].push_back(y);
        return;
    }
    int m = (l+r)/2;
    if(x <= m) Insert(2*nod, l, m);
    if(x > m) Insert(2*nod+1, m+1, r);
}

void Merge(int nod, int l, int r)
{
    if(l == r)
    {
        sort(Arb[nod].begin(), Arb[nod].end());
        Arb[nod].push_back(int(2e9));
        return;
    }
    int m = (l+r)/2;
    Merge(2*nod, l, m);
    Merge(2*nod+1, m+1, r);
    Arb[nod].resize(Arb[2*nod].size() + Arb[2*nod+1].size());
    merge(Arb[2*nod].begin(), Arb[2*nod].end(), Arb[2*nod+1].begin(), Arb[2*nod+1].end(), Arb[nod].begin());
}

void Query(int nod, int l, int r)
{
    if(P[l].x >= x and P[r].x <= y)
    {
        int p1 = lower_bound(Arb[nod].begin(), Arb[nod].end(), a) - Arb[nod].begin();
        int p2 = upper_bound(Arb[nod].begin(), Arb[nod].end(), b) - Arb[nod].begin();
        sol += p2 - p1;
        return;
    }
    int m = (l+r)/2;
    if(x <= P[m].x) Query(2*nod, l, m);
    if(y >= P[m+1].x) Query(2*nod+1, m+1, r);
}

int main()
{
    freopen("zoo.in", "r", stdin);
    ofstream fo("zoo.out");
    fread(buff, 1, DIM, stdin);
    get(n);
    for(i = 1; i <= n; i++)
    {
        get(P[i].x);
        get(P[i].y);
    }
    sort(P+1, P+n+1, cmp);
    for(i = 1; i <= n; i++)
    {
        x = i; y = P[i].y;
        Insert(1, 1, n);
    }
    Merge(1, 1, n);
    get(m);
    for(i = 1; i <= m; i++)
    {
        get(x); get(a); get(y); get(b);
        y = min(P[n].x, y);
        x = max(P[1].x, x);
        sol = 0;
        Query(1, 1, n);
        fo << sol << "\n";
    }
    return 0;
}