Cod sursa(job #829736)

Utilizator maritimCristian Lambru maritim Data 5 decembrie 2012 19:46:59
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

FILE *f = fopen("zoo.in","r");
FILE *g = fopen("zoo.out","w");

typedef vector<int>::iterator it;

struct nodAINT
{
    int x;
    vector<int> L;
} ; 

#define MaxN 17000
#define MaxAINT 33000
#define mij ((li+ls)>>1)
#define fs (poz<<1)
#define fd ((poz<<1)+1)

int N,M,nrX,x1,y1,x2,y2,Sol,nrPoz,B[MaxN];
pair<int,int> A[MaxN];
nodAINT AINT[MaxAINT];

void citire(void)
{
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
        fscanf(f,"%d %d\n",&A[i].first,&A[i].second);
}

inline void interclasare(int poz,int s,int d)
{
    it i = AINT[s].L.begin(),j = AINT[d].L.begin();

    for(;i < AINT[s].L.end() && j < AINT[d].L.end();)
        if(*i < *j)
            AINT[poz].L.push_back(*i), ++i;
        else
            AINT[poz].L.push_back(*j), ++j;

    for(;i < AINT[s].L.end();i++)
        AINT[poz].L.push_back(*i);

    for(;j < AINT[d].L.end();j++)
        AINT[poz].L.push_back(*j);
}

void afisare(vector<int> A)
{
    for(it i=A.begin();i<A.end();i++)
        printf("%d ",*i);
    printf("\n");
}

void build(int li,int ls,int poz)
{
    if(li > ls)
        return ;
    if(li == ls)
    {
        for(++nrPoz;A[nrPoz].first == A[nrPoz+1].first && nrPoz<N;++nrPoz)
            AINT[poz].L.push_back(A[nrPoz].second);
        AINT[poz].L.push_back(A[nrPoz].second);
        return ;
    }

    build(li,mij,fs);
    build(mij+1,ls,fd);

    interclasare(poz,fs,fd);
}

void normalizare(void)
{
    int i;
    B[0] = -1;
    
    for(nrX=0,i=1;i<=N;++i)
        if(B[nrX] != A[i].first)
            B[++nrX] = A[i].first;
}

inline int pStanga(vector<int> V)
{
    int li = 0,ls = V.size()-1;

    while(li <= ls)
        if(V[mij] >= y1)
            ls = mij-1;
        else
            li = mij+1;

    return li;
}

inline int pDreapta(vector<int> V)
{
    int li = 0,ls = V.size()-1;

    while(li <= ls)
        if(V[mij] <= y2)
            li = mij+1;
        else
            ls = mij-1;

    return li;
}

inline int puncte(vector<int> V)
{
    if(V.front() > y2 || V.back() < y1)
        return 0;

    return pDreapta(V)-pStanga(V); 
}

inline int querry(int li,int ls,int poz)
{
    int Sum = 0;

    if(x1 <= B[li] && B[ls] <= x2)
        return puncte(AINT[poz].L);

    if(x1 <= B[mij])
        Sum += querry(li,mij,fs);
    if(x2 > B[mij])
        Sum += querry(mij+1,ls,fd);

    return Sum;
}

void Rezolvare(void)
{
    sort(A+1,A+N+1);
    normalizare();

    build(1,nrX,1);

    //fscanf(f,"%d ",&M);
    //for(int i=1;i<=M;i++)
    //{
    //    fscanf(f,"%d %d %d %d\n",&x1,&y1,&x2,&y2);
    //    fprintf(g,"%d\n",querry(1,nrX,1));
    //}
}

int main()
{
    citire();
    Rezolvare();

    //for(it i=AINT[1].L.begin();i<AINT[1].L.end();i++)
    //    printf("%d ",*i);
}