Cod sursa(job #2455996)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 13 septembrie 2019 11:47:52
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.89 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;
    }

    void aranjare()
    {
        SegmentTree *now = this;

        sort(now -> v.begin(), now -> v.end());

        if(now -> st != nullptr)
            now -> st -> aranjare();

        if(now -> dr != nullptr)
            now -> dr -> aranjare();
    }

};

SegmentTree *arb = new SegmentTree;

void upd(long long &x)
{
    x = x + Bound + 1;
}

main()
{
    InParser fin("zoo.in");

    arb -> l = 1LL;
    arb -> r = Bound * 2 + 1;

    int n;
    fin >> n;

    while(n--)
    {
        long long x, y;
        fin >> x >> y;

        upd(x);
        upd(y);

        arb -> update(x, y);
    }

    arb -> aranjare();

    fin >> n;

    while(n--)
    {
        long long x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        upd(x1);
        upd(y1);
        upd(x2);
        upd(y2);

        int p = arb -> query(x1, y1, x2, y2);

        fout << p << '\n';
    }
}