Cod sursa(job #2522965)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 13 ianuarie 2020 16:11:53
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
//---------------------------------------------------
///Globale
int n,m,nr,raspuns[100001];
struct punct
{
	long long x,y;
} v[16001];
struct intrebare
{
	long long x,y,y2,nr;
} querry[200001];
struct trie
{
	int val;
	trie *fii[2];
};
trie *t = new trie();
bitset<100001>ap;
//---------------------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//---------------------------------------------------
int main()
{
	citire();
	rezolvare();
	afisare();
	return 0;
}
//---------------------------------------------------
void afisare()
{
	for(int i = 1; i <= m; ++i)
		g << raspuns[i] << '\n';
}
//---------------------------------------------------
int cauta(long long in,long long sf,long long st,long long dr,trie *nod)
{
    if(in == st && sf == dr)
        return nod -> val;
    long long mij = (in + sf) / 2;
    if(mij < st)
    {
        if(nod -> fii[1] == NULL)
            return 0;
        return cauta(mij + 1,sf,st,dr,nod -> fii[1]);
    }
    if(mij >= dr)
    {
        if(nod -> fii[0] == NULL)
            return 0;
        return cauta(in,mij,st,dr,nod -> fii[0]);
    }
    int x = 0;
    if(nod -> fii[0] != NULL)
        x = cauta(in,mij,st,mij,nod -> fii[0]);
    if(nod -> fii[1] != NULL)
        x += cauta(mij + 1,sf,mij + 1,dr,nod -> fii[1]);
    return x;
}
//---------------------------------------------------
void update(long long in,long long sf,long long poz,trie *nod)
{
	if(in == sf)
	{
		nod -> val++;
		return;
	}
	long long mij = (in + sf) / 2;
	if(mij >= poz)
    {
        if(nod -> fii[0] == NULL)
            nod -> fii[0] = new trie();
        update(in,mij,poz,nod -> fii[0]);
    }
    else
    {
        if(nod -> fii[1] == NULL)
            nod -> fii[1] = new trie();
        update(mij + 1,sf,poz,nod -> fii[1]);
    }
    int x = 0;
    if(nod -> fii[0] != NULL)
        x = nod -> fii[0] -> val;
    if(nod -> fii[1] != NULL)
        x += nod -> fii[1] -> val;
    nod -> val = x;
}
//---------------------------------------------------
bool compara(punct a,punct b)
{
	return a.x < b.x;
}
//---------------------------------------------------
bool compara2(intrebare a,intrebare b)
{
	return a.x < b.x;
}
//---------------------------------------------------
void rezolvare()
{
	sort(v + 1,v + n + 1,compara);
	sort(querry + 1,querry + nr + 1,compara2);
	int i = 1;
	int j = 1;
	while(i <= n && j <= nr)
		if(v[i].x <= querry[j].x)
		{
			update(0,4000000000,v[i].y + 2000000000,t);
			i++;
		}
		else
		{
			int x = cauta(0,4000000000,querry[j].y + 2000000000,querry[j].y2 + 2000000000,t);
			if(ap[querry[j].nr] == 0)
				raspuns[querry[j].nr] -= x;
			else
				raspuns[querry[j].nr] += x;
            ap[querry[j].nr] = 1;
			j++;
		}
    while(j <= nr)
    {
        int x = cauta(0,4000000000,querry[j].y + 2000000000,querry[j].y2 + 2000000000,t);
        if(ap[querry[j].nr] == 0)
            raspuns[querry[j].nr] -= x;
        else
            raspuns[querry[j].nr] += x;
        ap[querry[j].nr] = 1;
        j++;
    }
}
//---------------------------------------------------
void citire()
{
	f >> n;
	for(int i = 1; i <= n; ++i)
		f >> v[i].x >> v[i].y;
	f >> m;
	for(int i = 1; i <= m; ++i)
	{
		int x,y,x2,y2;
		f >> x >> y >> x2 >> y2;
		querry[++nr].x = x - 1;
		querry[nr].y = y;
		querry[nr].y2 = y2;
		querry[nr].nr = i;
		querry[++nr].x = x2;
		querry[nr].y = y;
		querry[nr].y2 = y2;
		querry[nr].nr = i;
	}

}