Cod sursa(job #1473568)

Utilizator MaligMamaliga cu smantana Malig Data 19 august 2015 17:29:07
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.06 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int N,M;

struct punct {
    int x,y;
}v[16010];

struct elem {
    int* vect;
}arb[524290];

bool cmp(punct,punct);
void formeaza_arb(int,int,int);
int query(int,int,int,int,int,int,int);
int binary_s(int*,int,int,int);

int main()
{
    f>>N;
    FOR (i,1,N) {
        f>>v[i].x>>v[i].y;
    }
    sort(v+1,v+N+1,cmp);
    /*FOR (i,1,N) {
        g<<v[i].x<<' '<<v[i].y<<'\n';
    }
    g<<'\n';*/
    formeaza_arb(1,1,N);
    /*int x=3;
    FOR (i,1,5) {
        g<<arb[x].vect[i]<<'\n';
    }
    g<<"\n\n";*/
    f>>M;
    FOR (i,1,M) {
        int x1,y1,x2,y2;
        f>>x1>>y1>>x2>>y2;
        g<<query(1,1,N,x1,y1,x2,y2)<<'\n';
    }
    f.close();g.close();
    return 0;
}

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

void formeaza_arb(int nod,int st,int dr) {
    //cout<<nod<<' '<<st<<' '<<dr<<'\n';
    arb[nod].vect=new int[dr-st+3];
    if (st==dr) {
        arb[nod].vect[1]=v[st].y;
        //cout<<nod<<' '<<st<<' '<<dr<<' '<<v[st].x<<' '<<v[st].y<<'\n';
    }
    else {
        int mij=(st+dr)>>1;
        formeaza_arb((nod<<1),st,mij);
        formeaza_arb((nod<<1)+1,mij+1,dr);
        int limst=mij-st+1,limdr=dr-(mij+1)+1;
        int i=1,j=1,dimvect=1;
        while (i<=limst && j<=limdr) {
            if (arb[(nod<<1)].vect[i]<arb[(nod<<1)+1].vect[j]) {
                arb[nod].vect[dimvect++]=arb[(nod<<1)].vect[i++];
            }
            else {
                arb[nod].vect[dimvect++]=arb[(nod<<1)+1].vect[j++];
            }
        }
        while (i<=limst) {
            arb[nod].vect[dimvect++]=arb[(nod<<1)].vect[i++];
        }
        while (j<=limdr) {
            arb[nod].vect[dimvect++]=arb[(nod<<1)+1].vect[j++];
        }
        /*cout<<nod<<'\n';
        FOR(i,1,dimvect) {
            cout<<arb[nod].vect[i].x<<' '<<arb[nod].vect[i].y<<'\n';
        }
        cout<<'\n';*/
    }
}

int query(int nod,int st,int dr,int x1,int y1,int x2,int y2) {
    //cout<<nod<<' '<<st<<' '<<dr<<'\n';
    if (x1<=v[st].x && v[dr].x<=x2) {
        int pozst,pozdr,dim=dr-st+1;
        pozst=binary_s(arb[nod].vect,dim,y1,1);
        pozdr=binary_s(arb[nod].vect,dim,y2,2);
        while (arb[nod].vect[pozst-1]==arb[nod].vect[pozst] && pozst-1>0) {
            --pozst;
        }
        while (arb[nod].vect[pozdr+1]==arb[nod].vect[pozdr] && pozdr+1<=dim) {
            ++pozdr;
        }
        if (pozdr>0 && pozdr<=dim && pozst>0 && pozst<=dim && pozst<=pozdr) {
            return pozdr-pozst+1;
        }
        return 0;
    }
    else if (st==dr) {
        return 0;
    }
    else {
        int mij=(st+dr)>>1;
        int rez=0;
        if (x1<=v[mij].x) {
            rez+=query((nod<<1),st,mij,x1,y1,x2,y2);
        }
        if (v[mij+1].x<=x2) {
            rez+=query((nod<<1)+1,mij+1,dr,x1,y1,x2,y2);
        }
        return rez;
    }
}

int binary_s(int* vect,int dim,int val,int tip) {
    int st=1,dr=dim;
    if (tip==1) {
        while (st<dr) {
            int mij=(st+dr)>>1;
            if (val<=vect[mij]) {
                dr=mij-1;
            }
            else if (val>vect[mij]) {
                st=mij+1;
            }
        }
        while (vect[st]<val && st<=dim) {
            ++st;
        }
        if (st>dim) {
            return dim+1;
        }
    }
    else {
        while (st<dr) {
            int mij=(st+dr)>>1;
            if (val<vect[mij]) {
                dr=mij-1;
            }
            else if (val>=vect[mij]) {
                st=mij+1;
            }
        }
        while (vect[st]>val && st>0) {
            --st;
        }
        if (st==0) {
            return -1;
        }
    }
    return st;
}