Cod sursa(job #933352)

Utilizator visanrVisan Radu visanr Data 29 martie 2013 21:27:40
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

#define Nmax 16010
#define x first
#define y second
#define LeftSon (Node << 1)
#define RightSon ((Node << 1) + 1)
#define PI pair<int, int>
#define pb push_back
#define Inf 2000000001

int N, M, Pos, Val, Ans, Xmin, Xmax, Ymin, Ymax;
vector<int> Aint[4 * Nmax];
PI V[Nmax];

void Update(int Node, int Left, int Right)
{
    if(Left == Right)
    {
        Aint[Node].pb(Val);
        return ;
    }
    int Mid = (Left + Right) / 2;
    if(Pos <= Mid) Update(LeftSon, Left, Mid);
    else Update(RightSon, Mid + 1, Right);
}

void SolveTree(int Node, int Left, int Right)
{
    if(Left > Right) return ;
    if(Left == Right)
    {
        Aint[Node].pb(Inf);
        sort(Aint[Node].begin(), Aint[Node].end());
        return ;
    }
    int Mid = (Left + Right) / 2;
    SolveTree(LeftSon, Left, Mid);
    SolveTree(RightSon, Mid + 1, Right);

    Aint[Node].resize(Aint[LeftSon].size() + Aint[RightSon].size());
    merge(Aint[LeftSon].begin(), Aint[LeftSon].end(), Aint[RightSon].begin(), Aint[RightSon].end(), Aint[Node].begin());
}

void BuildTree()
{
    for(int i = 1; i <= N; ++ i)
    {
        Pos = i; Val = V[i].y;
        Update(1, 1, N);
    }
    SolveTree(1, 1, N);
}

void Query(int Node, int Left, int Right)
{
    if(Xmin <= V[Left].x && V[Right].x <= Xmax)
    {
        Ans += (upper_bound(Aint[Node].begin(), Aint[Node].end(), Ymax)) - (lower_bound(Aint[Node].begin(), Aint[Node].end(), Ymin));
        return ;
    }
    if(Left >= Right) return ;
    int Mid = (Left + Right) / 2;
    if(Xmin <= V[Mid].x) Query(LeftSon, Left, Mid);
    if(V[Mid].x <= Xmax) Query(RightSon, Mid + 1, Right);
}

const int MaxB = 1000000;
char Buf[MaxB];
int Ptr = 0;

int GetInt()
{
    int Ans = 0, Sign = 1;
    while(!isdigit(Buf[Ptr]))
    {
        if(Buf[Ptr] == '-') Sign = -1;
        if(++Ptr >= MaxB) fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    while(isdigit(Buf[Ptr]))
    {
        Ans = Ans * 10 + Buf[Ptr] - '0';
        if(++Ptr >= MaxB) fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    return Ans * Sign;
}

int main()
{
    //Sortez punctele dupa X
    //Imi tin in Aint[Node] - toate valorile Y ce se gasesc in vectorul de puncte in intervalul corespunzator din Node
    //Tin sortate valorile Y
    //Si fac merge de la fii
    //Pt un query, descompun intervalul [Xmin, Xmax] in intervale mai mici, cele din arborele de intervale
    //Fac 2 cautari binare ca sa aflu cati Y-i sunt in acel interval si sunt intre Ymin si Ymax

    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    int i;
    N = GetInt();
    for(i = 1; i <= N; ++ i)
    {
        V[i].x = GetInt();
        V[i].y = GetInt();
    }
    sort(V + 1, V + N + 1);
    BuildTree();
    M = GetInt();
    for(i = 1; i <= M; ++ i)
    {
        Xmin = GetInt();
        Ymin = GetInt();
        Xmax = GetInt();
        Ymax = GetInt();
        Ans = 0;
        Query(1, 1, N);
        printf("%i\n", Ans);
    }
    return 0;
}