Cod sursa(job #1123196)

Utilizator Eugen_VlasieFMI Vlasie Eugen Eugen_Vlasie Data 25 februarie 2014 23:21:20
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
struct pt{
    int x,y;
};
int cmp(pt nr1,pt nr2)
{
    if(nr1.x<nr2.x)
        return 1;
    return 0;
}
int x1,y11,k,x2,y2,n,i,m,j,ain[100100];
pt v[16010];
void act(int nod,int st,int dr)
{
    int mij;
    if(st==dr)
    {
        ain[nod]++;
        return;
    }
    mij=(st+dr)>>1;
    if(j<=mij)
        act(nod*2,st,mij);
    else
        act(nod*2+1,mij+1,dr);
    ain[nod]=ain[nod*2]+ain[1+nod*2];
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    f>>m;
    v[n+1].x=2000000005;
    v[0].x=-2000000005;
    for(i=1;i<=m;i++)
    {
        memset(ain,0,sizeof(ain));
        f>>x1>>y11>>x2>>y2;
        j=0;
        while(v[j].x<x1)
            j++;
        while(v[j].x<=x2)
        {
            if(v[j].y>=y11&&v[j].y<=y2)
            {
                act(1,1,n);
            }
            j++;
        }
        g<<ain[1]<<'\n';
    }
    return 0;
}