Cod sursa(job #1750519)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 30 august 2016 13:32:52
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#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;
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;
}

vector<int> aint[4*(MAXN+2*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++]);
    }
}

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

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

    return 0;
}