Cod sursa(job #1750458)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 30 august 2016 12:02:34
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 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);
}

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

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 (xdr < mat[mid+1].x)
		return query(lo, mid, ind<<1, xst, xdr, yst, ydr);
    if (xst > mat[mid].x)
		return query(mid+1, hi, (ind<<1)+1, xst, xdr, yst, ydr);
    return query(lo, mid, (ind<<1), xst, mat[mid].x, yst, ydr) +
		   query(mid+1, hi, (ind<<1)+1, mat[mid+1].x, xdr, yst, ydr);
}

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