Cod sursa(job #1750721)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 30 august 2016 20:19:15
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <unordered_map>
#define MAXN 16064
#define MAXM 100050
#define DIM 300000

using namespace std;

struct punct
{
    int x, y;
    punct(int x = 0, int y = 0) : x(x), y(y) { }
};
int n, m, cursor;
unsigned int MAX_VAL;
char buf[DIM];
punct mat[MAXN];
punct drlo[MAXM], drhi[MAXM];

char getChar()
{
    if (cursor == DIM) {
        fread(buf, 1, DIM, stdin);
        cursor = 0;
    }
    return buf[cursor];
}

int readInt()
{
    char c;
    for (c = getChar(); c != '-' && !(c >= '0' && c <= '9'); c = getChar())
        cursor++;
    int semn = 1, nr = 0;
    if (c == '-') {
        semn = -1;
        cursor++;
    }
    for (c = getChar(); c >= '0' && c <= '9'; c = getChar()) {
        nr = nr*10 + c-'0';
        cursor++;
    }
    return semn*nr;
}

void citire()
{
	n = readInt();
    for (int i = 1; i <= n; i++) {
        mat[i].x = readInt();
        mat[i].y = readInt();
    }
    m = readInt();
    for (int i = 1; i <= m; i++) {
        drlo[i].x = readInt();
        drlo[i].y = readInt();
        drhi[i].x = readInt();
        drhi[i].y = readInt();
    }
}

bool cmp(punct e, punct f)
{
    if (e.x != f.x) return e.x < f.x;
    return e.y < f.y;
}
unordered_map<unsigned int, unordered_map<unsigned int, int> > unm;

inline unsigned int zero(unsigned int x)
{
    unsigned int val = x & (x ^ (x-1));
    if (1ULL*x + val > MAX_VAL)
		return MAX_VAL-x;
	return val;
}

void update(unsigned int x, unsigned int y, int val)
{
    for (unsigned int i = x; i < MAX_VAL; i += zero(i))
		for (unsigned int j = y; j < MAX_VAL; j += zero(j))
            unm[i][j] += val;
}

int query(unsigned int x, unsigned int y)
{
	int rez = 0;
	for (unsigned int i = x; i > 0; i -= zero(i))
		for (unsigned int j = y; j > 0; j -= zero(j))
            rez += unm[i][j];
	return rez;
}

void init()
{
	unsigned int a = 2000000050;
    MAX_VAL = a*2;
    for (int i = 1; i <= n; i++)
		update(mat[i].x+a, mat[i].y+a, 1);
}

void solve()
{
	unsigned int a = 2000000050;
    for (int i = 1; i <= m; i++) {
        unsigned int x0 = drlo[i].x + a;
        unsigned int y0 = drlo[i].y + a;
        unsigned int x1 = drhi[i].x + a;
        unsigned int y1 = drhi[i].y + a;
        int rez = query(x1, y1) - query(x1, y0-1) - query(x0-1, y1) + query(x0-1, y0-1);
        printf("%d\n", rez);
    }
}

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

	fread(buf, 1, DIM, stdin);
    citire();
    init();
    solve();

    return 0;
}