Cod sursa(job #1750282)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 29 august 2016 21:00:43
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 16064
#define MAXM 100050

using namespace std;

struct punct
{
	int x, y;
	punct(int x = 0, int y = 0) : x(x), y(y) { }
};
int n, m;
punct mat[MAXN];
punct drlo[MAXN], drhi[MAXN];

void citire()
{
	scanf("%d", &n);
    for (int i = 1; i <= n; i++)
		scanf("%d %d", &mat[i].x, &mat[i].y);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
        scanf("%d %d %d %d", &drlo[i].x, &drlo[i].y, &drhi[i].x, &drhi[i].y);
}
vector<int> v;
void normalizare()
{
    for (int i = 1; i <= n; i++)
		v.push_back(mat[i].x);
	for (int i = 1; i <= m; i++) {
		v.push_back(drlo[i].x);
		v.push_back(drhi[i].x);
	}
	sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++)
		mat[i].x = lower_bound(v.begin(), v.end(), mat[i].x) - v.begin();
    for (int i = 1; i <= m; i++) {
		drlo[i].x = lower_bound(v.begin(), v.end(), drlo[i].x) - v.begin();
		drhi[i].x = lower_bound(v.begin(), v.end(), drhi[i].x) - v.begin();
    }
    v.clear();
	for (int i = 1; i <= n; i++)
		v.push_back(mat[i].y);
	for (int i = 1; i <= m; i++) {
		v.push_back(drlo[i].y);
		v.push_back(drhi[i].y);
	}
	sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++)
		mat[i].y = lower_bound(v.begin(), v.end(), mat[i].y) - v.begin();
    for (int i = 1; i <= m; i++) {
		drlo[i].y = lower_bound(v.begin(), v.end(), drlo[i].y) - v.begin();
		drhi[i].y = lower_bound(v.begin(), v.end(), drhi[i].y) - v.begin();
    }
}
bool cmp(punct e, punct f)
{
    if (e.x != f.x) return e.x < f.x;
    return e.y < f.y;
}

vector<int> aint[4*(MAXN+MAXM)];

void update(int lo, int hi, int ind, int &pos)
{
    if (lo == hi) {
        while (mat[pos].x == lo)
			aint[ind].push_back(mat[pos++].y);
		return;
    }
    int mid = (lo + hi) >> 1;
    update(lo, mid, ind<<1, pos);
    update(mid+1, hi, (ind<<1)+1, pos);
//    for (int i = 0, j = 0; i < aint[ind<<1].size() || j < aint[(ind<<1)+1].size(); ) {
//        if (i >= aint[ind<<1].size())
//			aint[ind].push_back(aint[(ind<<1)+1][j++]);
//        else if (j < aint[(ind<<1)+1].size() && aint[(ind<<1)+1][j] < aint[ind<<1][i])
//			aint[ind].push_back(aint[(ind<<1)+1][j++]);
//		else
//			aint[ind].push_back(aint[ind<<1][i++]);
//    }
	aint[ind].resize(aint[ind<<1].size() + aint[(ind<<1)+1].size());
	merge(aint[ind<<1].begin(), aint[ind<<1].end(),
		aint[(ind<<1)+1].begin(), aint[(ind<<1)+1].end(), aint[ind].begin());
}

void init()
{
    sort(mat+1, mat+n+1, cmp);
    int pos = 1;
    update(0, n+2*m, 1, pos);
}

int query(int lo, int hi, int ind, int xst, int xdr, int yst, int ydr)
{
    if (xst <= lo && hi <= xdr) {
        return upper_bound(aint[ind].begin(), aint[ind].end(), ydr) -
				lower_bound(aint[ind].begin(), aint[ind].end(), yst);
    }
    int cate = 0, mid = (lo + hi) >> 1;
    if (xst <= mid)
		cate += query(lo, mid, ind<<1, xst, xdr, yst, ydr);
    if (xdr > mid)
		cate += query(mid+1, hi, (ind<<1)+1, xst, xdr, yst, ydr);
	return cate;
}

void solve()
{
    for (int i = 1; i <= m; i++) {
        int rez = query(0, n+2*m, 1, drlo[i].x, drhi[i].x, drlo[i].y, drhi[i].y);
		printf("%d\n", rez);
    }
}

int main()
{
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);

	citire();
	normalizare();
	init();
	solve();

    return 0;
}