Cod sursa(job #1750750)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 30 august 2016 21:55:29
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 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();
    }
}

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;
}
unordered_map<int, unordered_map<int, int> > unm;

inline int zero(int x)
{
    return x & (x ^ (x-1));
}

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

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

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

void solve()
{
	int a = 1;
    for (int i = 1; i <= m; i++) {
        int x0 = drlo[i].x + a;
        int y0 = drlo[i].y + a;
        int x1 = drhi[i].x + a;
        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();
    normalizare();
    init();
    solve();

    return 0;
}