Cod sursa(job #2517819)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 4 ianuarie 2020 12:14:35
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <bits/stdc++.h>

using namespace std;
#define DIM 1000000
char buff[DIM];
int poz=0;
 
void citeste(int &numar)
{
     numar = 0;
     char semn='+';     
     while (buff[poz] < '0' || buff[poz] > '9')
     {     
          semn = buff[poz];
          if (++poz == DIM) 
               fread(buff,1,DIM,stdin),poz=0;
     }          
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM) 
               fread(buff,1,DIM,stdin),poz=0;               
     }     
     if (semn == '-')
          numar = -numar;
}
int n,m,x,y,xi,yi,cn,arboremi[(1<<16)+3],arborema[(1<<16)+3];pair <int,int> coord[16505];
int cb (int nr) {
	int i=0,step=1;
	for(;(step<<1)<=n;step<<=1);
	for(;step>0;step>>=1)
		if(i+step<=n && coord[i+step].first<nr)
			i+=step;
	return i;
}
int cb1 (int nr) {
	int i=0,step=1;
	for(;(step<<1)<=n;step<<=1);
	for(;step>0;step>>=1)
		if(i+step<=n && coord[i+step].first<=nr)
			i+=step;
	return i;
}
void build_arbore () {
	for(int i=cn;i<(cn<<1);++i)
		if(i-cn+1<=n)
			arboremi[i]=coord[i-cn+1].second,arborema[i]=coord[i-cn+1].second;
		else
			arboremi[i]=(1<<31),arborema[i]=(-1)*(1<<31);
	for(int i=cn-1;i>0;--i) 
		arborema[i]=max(arborema[(i<<1)],arborema[(i<<1)+1]),arboremi[i]=min(arboremi[(i<<1)],arboremi[(i<<1)+1]);
}
int querrys (int st,int dr, int cst, int cdr, int indexx) {
	if(cst>=st && cdr<=dr) {
		if(arborema[indexx]<=yi && arboremi[indexx]>=y)
			return cdr-cst+1;
		else if (cst!=cdr) {
			int mij=(cst+cdr)>>1;
			return querrys(st,dr,cst,mij,(indexx<<1))+querrys(st,dr,mij+1,cdr,(indexx<<1)+1);
		}
		return 0;
	}
	else {
		int mij=(cst+cdr)>>1,rez=0;
		if(mij>=st)
			rez+=querrys(st,dr,cst,mij,(indexx<<1));
		if(mij+1<=dr)
			rez+=querrys(st,dr,mij+1,cdr,(indexx<<1)+1);
		return rez;
	}
}
int main () {
	int poz1,poz2;
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	citeste(n);cn=n;
	if((cn & (cn-1))!=0) {
		for(int i=0;(cn & (cn-1))!=0;++i)
			if((cn & (1<<i))!=0) 
				cn^=(1<<i);
		cn<<=1;
	}
	for(int i=1;i<=n;++i)
		citeste(coord[i].first),citeste(coord[i].second);
	sort(coord+1,coord+n+1);build_arbore();
	citeste(m);++m;
	while(--m) {
		citeste(x);citeste(y);citeste(xi);citeste(yi);
		//scanf("%d%d%d%d", &x, &y, &xi, &yi);
		poz1=cb(x)+1;poz2=cb1(xi);
		if(poz1>poz2) {
			printf("0\n");
			continue;
		}
		if(coord[poz1].first<=xi && poz1<=n)
			printf("%d\n", querrys(poz1,poz2,1,cn,1));
		else
			printf("0\n");
	}
	return 0;
}