Cod sursa(job #1927333)

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

int N,M,Norm[MaxM*3],Size,X1,Y1,X2,Y2,Out[MaxM],Pos,Val,Start,End,T[MaxT];
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 p=1;
	for(int i=18;i>=0;i--)
	{
		if((p+(1<<i))<=Size&&Norm[p+(1<<i)]<=val)
			p+=1<<i;
	}
	return p;
}
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");
	
	fscanf(IN,"%d",&N);
	for(int i=1;i<=N;i++)
	{
		fscanf(IN,"%d%d",&L[i].x,&L[i].y);
		Norm[++Size]=L[i].y;
	}
	fscanf(IN,"%d",&M);
	for(int i=1;i<=M;i++)
	{
		fscanf(IN,"%d%d%d%d",&X1,&Y1,&X2,&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);
	for(int i=1;i<=N;i++)
	{
		Pos=L[i].y,Val=1;
		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);
		Out[Q[i].p]+=Val*Q[i].sign;
	}
	for(int i=1;i<=M;i++)
		fprintf(OUT,"%d\n",Out[i]);
	return 0;
}