Cod sursa(job #1750320)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 29 august 2016 21:48:22
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 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) {
		aint[ind].push_back(mat[lo].y);
		return;
    }
    int mid = (lo + hi) >> 1;
    update(lo, mid, ind<<1, pos);
    update(mid+1, hi, (ind<<1)+1, pos);
	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(1, n, 1, pos);
}

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

void solve()
{
    for (int i = 1; i <= m; i++) {
		drlo[i].x = max(drlo[i].x, mat[1].x);
		drhi[i].x = min(drhi[i].x, mat[n].x);
        int rez = query(1, n, 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;
}