Cod sursa(job #1774304)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 8 octombrie 2016 19:45:43
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2140000000
#define MaxT 100000000
#define MaxN 16005
#define MaxM 100005
#define MAX 131072
#define MAXS 15000000
using namespace std;
  
FILE *IN,*OUT;
int pos=0,out=0,sign,N,M,End,Pos,X1,X2,Y1,Y2,Size=0,Ans;
char f[MAX],Out[MAX],str[10];
int T[MaxT];
struct _Point
{
	int x,y;
}v[MaxN];
struct _Query
{
	int x,y,pos,sign;
}List[MaxM*4];
int O[MaxM];

inline void Write_Ch(char ch)
{
    Out[out++]=ch;
    if(out==MAX)
        fwrite(Out,MAX,1,OUT),out=0;
}
inline void Write_Int(int nr)
{
    int x=0;
    if(nr<0)Write_Ch('-'),nr=-nr;
    do
    {
        str[x++]=nr%10+'0';
        nr/=10;
    }
    while(nr);
    while(x>0)
        Write_Ch(str[--x]);
}
inline int min2(int a,int b)
{
    if (a<b) return a;
    else return b;
}
inline int max2(int a,int b)
{
    if (a>b) return a;
    else return b;
}
inline void Read(int &nr)
{
    sign=0;
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
    {
        if(f[pos]=='-')sign=1;
        pos++;
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=10*nr+f[pos++]-'0';
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    if(sign)nr=-nr;
}

bool cond(_Point a,_Point b)
{
	return a.y<b.y;
}
bool cond2(_Query a,_Query b)
{
	return a.y<b.y;
}
void Add(int x,int y,int Sign,int pos)
{
	Size++;
	List[Size].pos=pos;
	List[Size].x=x;
	List[Size].y=y;
	List[Size].sign=Sign;
}
void Update(int node,int start,int end)
{
	if(start==end)
		T[node]++;
	else
	{
		int mid=(start>>1)+(end>>1)+(start%2&&end%2&&(end<=0||start>=0));
		if(Pos>mid)Update(2*node+1,mid+1,end);
		else Update(2*node,start,mid);
		T[node]=T[2*node]+T[2*node+1];
	}
}
void Query(int node,int start,int end)
{
	if(end<=End)
		Ans+=T[node];
	else
	{
		int mid=(start>>1)+(end>>1)+(start%2&&end%2&&(end<=0||start>=0));
		if(mid<End)Query(2*node+1,mid+1,end);
		Query(2*node,start,mid);
	}
}

int main()
{
    IN=fopen("zoo.in","r");
    OUT=fopen("zoo.out","w");
    fread(f,1,MAX,IN);

	Read(N);
	for(int i=1;i<=N;i++)
	{
		Read(v[i].x);
		Read(v[i].y);
	}
	sort(v+1,v+1+N,cond);
	Read(M);
	for(int i=1;i<=M;i++)
	{
		Read(X1),Read(Y1),Read(X2),Read(Y2);
		Add(X1-1,Y1-1,1,i);
		Add(X2,Y2,1,i);
		Add(X1-1,Y2,-1,i);
		Add(X2,Y1-1,-1,i);
	}
	sort(List+1,List+1+4*M,cond2);
	int j=1;
	for(int i=1;i<=4*M;i++)
	{
		while(j<=N&&v[j].y<=List[i].y)
		{
			Pos=v[j].x;
			Update(1,-MAXS,MAXS);
			j++;
		}
		End=List[i].x;
		Ans=0;
		Query(1,-MAXS,MAXS);
		O[List[i].pos]+=Ans*List[i].sign;
	}
	for(int i=1;i<=M;i++)
		Write_Int(O[i]),Write_Ch('\n');
    if(out>0)fwrite(Out,1,out,OUT);
    return 0;
}