Cod sursa(job #2456087)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 13 septembrie 2019 17:04:23
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.24 kb
#include <bits/stdc++.h>

using namespace std;
	
ofstream fout("zoo.out");
	
class InParser {

private:
	
	FILE *fin;
	
	char *buff;
	int sp;
	
	char read_ch() 
	{
		++sp;
	
		if(sp == 4096) 
		{
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		
		return buff[sp];
	}
	
public:
	
	InParser(const char* nume) 
	{
	
		fin = fopen(nume, "r");
	
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) 
	{
	
		char c;
	
		while (!isdigit(c = read_ch()) && c != '-');
	
		int sgn = 1;
	
		if(c == '-') 
		{
			n = 0;
			sgn = -1;
		} 
		else 
		{
			n = c - '0';
		}
	
		while(isdigit(c = read_ch()))
			n = 10 * n + c - '0';
	
		n *= sgn;
	
		return *this;
	}
	
	InParser& operator >> (long long &n) 
	{
		char c;
		n = 0;
	
		while(!isdigit(c = read_ch()) && c != '-');
	
		long long sgn = 1;
	
		if(c == '-') 
		{
			n = 0;
			sgn = -1;
		} 
		else 
		{
			n = c - '0';
		}
	
		while(isdigit(c = read_ch())) 
			n = 10 * n + c - '0';
	
		n *= sgn;
	
		return *this;
	}
};
 
const long long Bound = 2e9;
 
struct SegmentTree
{
    long long l;
    long long r;
 
    vector <long long> v;
 
    SegmentTree *st;
    SegmentTree *dr;
 
    SegmentTree()
    {
        st = nullptr;
        dr = nullptr;
 
        l = 0LL;
        r = 0LL;
 
        v.clear();
    }
 
    void Expand(int dir)
    {
        SegmentTree *now = this;
 
        if(dir == 0)
        {
            if(now -> st == nullptr)
            {
                now -> st = new SegmentTree;
                now -> st -> l = now -> l;
                now -> st -> r = (now -> l + now -> r) / 2;
            }
        }
        else
        {
            if(now -> dr == nullptr)
            {
                now -> dr = new SegmentTree;
                now -> dr -> l = (now -> l + now -> r) / 2 + 1;
                now -> dr -> r = now -> r;
            }
        }
    }
 
    void update(long long linie, long long col)
    {
        SegmentTree *now = this;
 
        now -> v.push_back(col);
 
        if(l == r)
        {
            return ;
        }
 
        long long mid = (now -> l + now -> r) / 2;
 
        if(linie <= mid)
        {
            now -> Expand(0);
            now -> st -> update(linie, col);
        }
        else
        {
            now -> Expand(1);
            now -> dr -> update(linie, col);
        }
    }
 
    int get(vector <long long> v, long long x, long long y)
    {
        if(v.size() == 0)
            return 0;
 
        int n = v.size();
        int l = 0;
        int r = n - 1;
 
        int itr1 = 0;
        int itr2 = 0;
 
        if(v[r] < x)
            return 0;
 
        if(v[l] > y)
            return 0;
 
        while(l <= r)
        {
            int mid = (l + r) / 2;
 
            if(v[mid] < x)
            {
                l = mid + 1;
            }
            else
            {
                itr1 = mid;
                r = mid - 1;
            }
        }
 
        if(v[itr1] > y)
            return 0;
 
        l = 0;
        r = n - 1;
 
        while(l <= r)
        {
            int mid = (l + r) / 2;
 
            if(v[mid] > y)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
                itr2 = mid;
            }
        }
 
        if(v[itr2] < x)
            return 0;
 
        return itr2 - itr1 + 1;
    }
 
    int query(long long x1, long long y1, long long x2, long long y2)
    {
        SegmentTree *now = this;
 
        long long l = now -> l;
        long long r = now -> r;
 
        if(x1 <= l && r <= x2)
        {
            return get(now -> v, y1, y2);
        }
 
        long long mid = (l + r) / 2;
 
        int sum = 0;
 
        if(x1 <= mid && now -> st != nullptr)
            sum += now -> st -> query(x1, y1, x2, y2);
 
        if(x2 > mid && now -> dr != nullptr)
            sum += now -> dr -> query(x1, y1, x2, y2);
 
        return sum;
    }
};
 
SegmentTree *arb = new SegmentTree;

struct Point
{
	int x, y;
	int pos;
};
 
vector <Point> t;

bool cmp1(Point x, Point y)
{
	return x.x <= y.x;
}

bool cmp2(Point x, Point y)
{
	return x.y <= y.y;
}
 
main()
{
    InParser fin("zoo.in");
 
    arb -> l = 1LL;
 
    int n;
    fin >> n;
 
    while(n--)
    {
        long long x, y;
        fin >> x >> y;
 
		t.push_back({x, y, 0});
    }
	
	int k = 1;
	
	sort(t.begin(), t.end(), cmp1);
	
	t[0].pos = 1;
	
	for(int i = 1; i < t.size(); i++)
	{
		if(t[i].x != t[i - 1].x)
			k++;
		
		t[i].pos = k;
	}
	
	arb -> r = k;
	
	sort(t.begin(), t.end(), cmp2);
	
	for(auto i : t)
		arb -> update(i.pos, i.y);
	
	sort(t.begin(), t.end(), cmp1);
	
    fin >> n;
 
    while(n--)
    {
        long long x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
		
		int it1 = 0;
		int it2 = 0;
		
		int l = 0;
		int r = t.size() - 1;
		
		while(l <= r)
		{
			int mid = (l + r) / 2;
			
			if(t[mid].x < x1)
			{
				l = mid + 1;
			}
			else
			{
				r = mid - 1;
				it1 = mid;
			}
		}
		
		l = 0;
		r = t.size() - 1;
		
		while(l <= r)
		{
			int mid = (l + r) / 2;
			
			if(t[mid].x > x2)
			{
				r = mid - 1;
			}
			else
			{
				l = mid + 1;
				it2 = mid;
			}
		}
		
		if(t[it1].x > x2 || t[it2].x < x1)
		{
			fout << 0 << '\n';
			continue;
		}
		
		x1 = t[it1].pos;
		x2 = t[it2].pos;
		
        int p = arb -> query(x1, y1, x2, y2);
 
        fout << p << '\n';
    }
}