Cod sursa(job #1229126)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 16 septembrie 2014 15:37:02
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

struct points
{
    int x,y;
    int indice;
    bool ok;
};

struct drept
{
    int x,y,w,z;
};

const int NMAX=16005;
const int MMAX=100005;

int n,m,sol[MMAX],AIB[NMAX];
vector<points>v[NMAX];
vector<points>::iterator it;
points a[NMAX],linie[MMAX],coloana[MMAX];
drept b[MMAX];

inline bool cmp1(const points A,const points B)
{
    return A.x<B.x;
}

inline bool cmp2(const points A,const points B)
{
    return A.y<B.y;
}

inline int zeros(int x)
{
    return x^(x&(x-1));
}

inline void UPDATE(int poz,int val)
{
    for (;poz<=n;poz+=zeros(poz)) AIB[poz]+=val;
}

inline int QUERY(int poz)
{
    int i,rez=0;
    for (i=poz;i>=1;i-=zeros(i)) rez+=AIB[i];
    return rez;
}

int main()
{
    int i,aux,st,dr,mij;
    points d;
    fin>>n;
    for (i=1;i<=n;i++) fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp1);
    for (i=1;i<=n;i++) a[i].indice=i;
    fin>>m;
    for (i=1;i<=m;i++)
        {
            fin>>b[i].x>>b[i].y>>b[i].w>>b[i].z;
            st=1;dr=n;
            while (st<=dr)
                {
                    mij=(st+dr)>>1;
                    if (a[mij].x>=b[i].x) {linie[i].x=mij;dr=mij-1;}
                    else st=mij+1;
                }

            st=1;dr=n;
            while (st<=dr)
                {
                    mij=(st+dr)>>1;
                    if (a[mij].x<=b[i].w) {linie[i].y=mij;st=mij+1;}
                    else dr=mij-1;
                }
        }
    sort(a+1,a+n+1,cmp2);
    for (i=1;i<=m;i++)
        {
            st=1;dr=n;
            while (st<=dr)
                {
                    mij=(st+dr)>>1;
                    if (a[mij].y>=b[i].y) {coloana[i].x=mij;dr=mij-1;}
                    else st=mij+1;
                }

            st=1;dr=n;
            while (st<=dr)
                {
                    mij=(st+dr)>>1;
                    if (a[mij].y<=b[i].z) {coloana[i].y=mij;st=mij+1;}
                    else dr=mij-1;
                }
            if (linie[i].x!=0 && linie[i].y!=0 && linie[i].x<=linie[i].y)
                if (coloana[i].x!=0 && coloana[i].y!=0 && coloana[i].x<=coloana[i].y)
                    {
                        d.x=linie[i].x;
                        d.y=linie[i].y;
                        d.indice=i;

                        d.ok=0;
                        v[coloana[i].x - 1].push_back(d);

                        d.ok=1;
                        v[coloana[i].y].push_back(d);
                    }
        }
    for (i=1;i<=n;i++)
        {
            UPDATE(a[i].indice,1);
            for (it=v[i].begin();it!=v[i].end();it++)
                {
                    d=*it;
                    aux=QUERY(d.y)-QUERY(d.x - 1);
                    if (d.ok==0) sol[d.indice]-=aux;
                    else sol[d.indice]+=aux;
                }
        }

    for (i=1;i<=m;i++) fout<<sol[i]<<"\n";
    return 0;
}