Cod sursa(job #2618805)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 26 mai 2020 12:42:03
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <bits/stdc++.h>
#define maxn 16005

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;
	}
};

InParser fin ("zoo.in");
std::ofstream fout ("zoo.out");

struct Point{
    int x, y;
}p[maxn];
bool sortX (Point a, Point b){
        return a.x < b.x;
}
std::vector <int> tree[2*maxn];

void buildTree (int node, int left, int right){
    if (left == right){
        tree[node].push_back (p[left].y);
        return;
    }
    int mid = (left + right) / 2;
    buildTree (2*node+1, left, mid);
    buildTree (2*node+2, mid+1, right);


    tree[node].resize (tree[2*node+1].size() + tree[2*node+2].size());
    std::merge (tree[2*node+1].begin(), tree[2*node+1].end(),
                tree[2*node+2].begin(), tree[2*node+2].end(),
                tree[node].begin());
}

int lowerBound (int left, int right, int val){
    int mid;
    while (left <= right){
        mid = (left + right) / 2;
        if (p[mid].x >= val and (mid == 0 or p[mid-1].x < val))
            return mid;
        if (p[mid].x >= val)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

int upperBound (int left, int right, int val){
    int mid;
    while (left <= right){
        mid = (left + right) / 2;
        if (p[mid].x > val and (mid == 0 or p[mid-1].x < val))
            return mid;
        if (p[mid].x > val)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

int query (int node, int left, int right, int l, int r, int y1, int y2){
    if (left > right or left > r or right < l)
        return 0;
    if (l <= left and right <= r){
        int p1 = std::lower_bound (tree[node].begin(), tree[node].end(), y1) - tree[node].begin();
        int p2 = std::upper_bound (tree[node].begin(), tree[node].end(), y2) - tree[node].begin();
        return p2 - p1;
    }
    int mid = (left + right) / 2;
    return query (2*node+1, left, mid, l, r, y1, y2) +
           query (2*node+2, mid+1, right, l, r, y1, y2);
}

int main()
{
    int n, i;
    fin >> n;
    for (i=0; i<n; i++)
        fin >> p[i].x >> p[i].y;
    std::sort (p, p+n, sortX);
    buildTree (0, 0, n-1);

    for (i=0; i<2*n; i++){
        fout << i << " : ";
        for (auto j:tree[i])
            fout << j << ' ' ;
        fout << '\n';
    }

    int Q, x1, x2, y1, y2, left, right;
    fin >> Q;
    while (Q --){
        fin >> x1 >> y1 >> x2 >> y2;
        left = lowerBound (0, n-1, x1);
        right = upperBound (0, n-1, x2);
        fout << query (0, 0, n-1, left, right-1, y1, y2) << '\n';
    }
    return 0;
}