Cod sursa(job #870869)

Utilizator loginLogin Iustin Anca login Data 4 februarie 2013 02:57:17
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
# include <fstream>
# include <iostream>
# include <algorithm>
# define DIM 100003
# define MAX 20000
using namespace std;
struct pct{
	int x, y, t;
	inline friend bool operator < (const pct &a, const pct &b) {
		if (a.x<b.x || (a.x==b.x && a.y<b.y) || (a.x==b.x && a.y==b.y && a.t<b.t))return true;
		return false;
	}
}v[4*DIM], w[MAX];

int n, m, y[MAX], N, Q;
short a[MAX], s[DIM];

void read ()
{
	ifstream fin ("zoo.in");
    fin>>n;
    fin.get();
    char l[100];
    for(int j=1;j<=n;++j)
    {
        fin.getline(l, 100);
        int nr = 0, i=0, s=1;
        for(i=0;l[i];++i)
        {
            if (l[i]=='-')
                s=-1;
            else if (l[i]>='0' && l[i]<='9')
                nr=10*nr+l[i]-'0';
            else
            {
                nr*=s;
                w[j].x=nr;
                break;
            }
        }        
        nr = 0;
        s=1;
        for(++i;l[i];++i)
            if (l[i]=='-')
                s=-1;
            else if (l[i]>='0' && l[i]<='9')
                nr=10*nr+l[i]-'0';
        nr*=s;
        w[j].y = nr;
		y[j+5]=nr;

    }
    int x1, x2, y1, y2, p;
    fin>>m;fin.get();
    for(int j=1;j<=m;++j)
    {
        fin.getline(l, 100);
        int nr = 0, i=0, s=1;
        for(i=0;l[i];++i)
            if (l[i]=='-')
                s=-1;
            else if (l[i]>='0' && l[i]<='9')
                nr=10*nr+l[i]-'0';
            else
            {
                nr*=s;
                x1=nr;
                break;
            }
        nr = 0;
        s=1;
        for(++i;l[i];++i)
            if (l[i]=='-')
                s=-1;
            else if (l[i]>='0' && l[i]<='9')
                nr=10*nr+l[i]-'0';
            else
            {
                nr*=s;
                y1=nr;
                break;
            }
        nr = 0;
        s=1;
        for(++i;l[i];++i)
            if (l[i]=='-')
                s=-1;
            else if (l[i]>='0' && l[i]<='9')
                nr=10*nr+l[i]-'0';
            else
            {
                nr*=s;
                x2=nr;
                break;
            }
        nr = 0;
        s=1;
        for(++i;l[i];++i)
            if (l[i]=='-')
                s=-1;
            else if (l[i]>='0' && l[i]<='9')
                nr=10*nr+l[i]-'0';
             
        nr*=s;
        y2=nr;
		
		--x1;--y1;p=j<<1;
		v[N+1].x=x1;v[N+1].y=y1;v[N+1].t=p;
		v[N+2].x=x2;v[N+2].y=y2;v[N+2].t=p;
		v[N+3].x=x1;v[N+3].y=y2;v[N+3].t=p+1;
		v[N+4].x=x2;v[N+4].y=y1;v[N+4].t=p+1;
		N+=4;
	}
}

void upd (int p)
{
	while(p<=Q)
	{
		++a[p];
		p+=p^(p&(p-1));
	}
}

short query (int p)
{
	short r = 0;
	while(p>0)
	{
		r+=a[p];
		p-=p^(p&(p-1));
	}
	return r;
}

int poz (int Y)
{
	int r=0;
	for(int st=1, dr=Q, mij=(st+dr)>>1;st<=dr;mij=(st+dr)>>1)
		if (y[mij]==Y)
			return mij;
		else if (y[mij]<Y)
		{
			r=mij;
			st=mij+1;
		}
		else
			dr=mij-1;
	return r;
}		

void solve ()
{
	sort(y+6, y+n+6);
	for(int i=1;i<=n;++i)
		if(i==1 || y[i+4]!=y[i+5])
			y[++Q]=y[i+5];			
	
	sort(v+1, v+N+1);
	sort(w+1, w+n+1);
	int i=1, j=1;
	for(;i<=N && j<=n;)
		if (w[j]<v[i])
			upd(poz(w[j].y)),
			++j;
		else
		{
			int q = v[i].t>>1;
			s[q] += (q<<1==v[i].t?1:-1) * query(poz(v[i].y));
			++i;
		}
	while(i<=N)
	{
		int q = v[i].t>>1;
		s[q] += (q<<1==v[i].t?1:-1) * query(poz(v[i].y));
		++i;
	}
}

int main ()
{
	read ();
	solve ();
	
	freopen("zoo.out", "w", stdout);
	for(int i=1;i<=m;++i)
		printf("%d\n", s[i]);
		
	return 0;
}