Cod sursa(job #1927341)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 15 martie 2017 02:01:33
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MaxN 20005
#define MaxT 700005
#define MaxM 120005
#define MAX 131072
using namespace std;
   
FILE*IN,*OUT;

int pos=0,out=0,sign;
char f[MAX],Out[MAX],str[10];
int N,M,Norm[MaxM*3],Size,X1,Y1,X2,Y2,O[MaxM],Pos,Val,Start,End,T[MaxT];
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 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;
}
struct Point
{
	int x,y;
}L[MaxN];
struct query
{
	int x,y,sign,p;
}Q[MaxM*4];
bool cond(Point a,Point b)
{
	return a.x<b.x;
}
bool cond2(query a,query b)
{
	return a.x<b.x;
}
int Search(int val)
{
	int lw=1,hi=Size,mid;
	while(lw<=hi)
	{
		mid=(lw+hi)>>1;
		if(Norm[mid]<val)
			lw=mid+1;
		else if(Norm[mid]>val)
			hi=mid-1;
		else return mid;
	}
}
void Delete_Copy()
{
	int pos=0;
	for(int i=1;i<=Size;i++)
	{
		if(Norm[pos]!=Norm[i])
			Norm[++pos]=Norm[i];
	}
	Size=pos;
}
void Update(int node,int start,int end)
{
	T[node]+=Val;
	if(start==end)
		return;
	else
	{
		int mid=(start+end)>>1;
		if(Pos>mid)Update(2*node+1,mid+1,end);
		else Update(2*node,start,mid);
	}
}
void Query(int node,int start,int end)
{
	if(Start<=start)
		Val+=T[node];
	else
	{
		int mid=(start+end)>>1;
		Query(2*node+1,mid+1,end);
		if(Start<=mid)Query(2*node,start,mid);
	}
}
int main()
{
    IN=fopen("zoo.in","r");
    OUT=fopen("zoo.out","w");
	
	Read(N);
	for(int i=1;i<=N;i++)
	{
		Read(L[i].x),Read(L[i].y);
		Norm[++Size]=L[i].y;
	}
	Read(M);
	for(int i=1;i<=M;i++)
	{
		Read(X1),Read(Y1),Read(X2),Read(Y2);
		Q[i*4-3].x=X1,Q[i*4-3].y=Y1,Q[i*4-3].sign=1;
		Q[i*4-2].x=X1,Q[i*4-2].y=Y2+1,Q[i*4-2].sign=-1;
		Q[i*4-1].x=X2+1,Q[i*4-1].y=Y1,Q[i*4-1].sign=-1;
		Q[i*4].x=X2+1,Q[i*4].y=Y2+1,Q[i*4].sign=1;
		Q[i*4-3].p=Q[i*4-2].p=Q[i*4-1].p=Q[i*4].p=i;
		Norm[++Size]=Y1;
		Norm[++Size]=Y2+1;
	}
	sort(Norm+1,Norm+1+Size);
	Delete_Copy();
	for(int i=1;i<=N;i++)
		L[i].y=Search(L[i].y);
	for(int i=1;i<=4*M;i++)
		Q[i].y=Search(Q[i].y);
	sort(L+1,L+1+N,cond);
	sort(Q+1,Q+1+4*M,cond2);
	Val=1;
	for(int i=1;i<=N;i++)
	{
		Pos=L[i].y;
		Update(1,1,216005);
	}
	int start=1;
	for(int i=1;i<=4*M;i++)
	{
		Val=-1;
		while(start<=N&&L[start].x<Q[i].x)
			Pos=L[start++].y,Update(1,1,216005);
		Val=0;
		Start=Q[i].y;
		Query(1,1,216005);
		O[Q[i].p]+=Val*Q[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;
}