Cod sursa(job #852726)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 11 ianuarie 2013 17:36:22
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdio>

#define MAX 16005
#define RMAX 100005
#define BMAX 50000
#define INF 2000000050
#define PII pair<int, int>
#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

int N, M, maxim, poz, X[MAX], Y[MAX], AIB[MAX], ans[RMAX];
char buff[BMAX];
PII V[MAX];

struct PUNCT
{
    int X, Y, ind, sign;
}add;
vector<PUNCT> Q;

struct RECT
{
    int x1, y1, x2, y2;
} R[RMAX];

void cit(int &X)
{
    X = 0; int sign = 1;
    while((buff[poz] < '0' || buff[poz] > '9') && buff[poz] != '-')
    {
        poz++;
        if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    }
    if(buff[poz] == '-') sign = -1, poz++;
    if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    while(buff[poz] >= '0' && buff[poz] <= '9')
    {
        X = X * 10 + buff[poz++] - '0';
        if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    }
    X *= sign;
}

void citire()
{
    freopen("zoo.in", "r", stdin);
    fread(buff, 1, BMAX, stdin); cit(N);
    for(int i = 1; i <= N; i++) cit(V[i].f), cit(V[i].s);
    cit(M); sort(V + 1, V + N + 1);
    for(int i = 1; i <= M; i++)
    {
        cit(R[i].x1), cit(R[i].y1), cit(R[i].x2), cit(R[i].y2);
    } fclose(stdin);
}

void normalize()
{
    Y[++Y[0]] = -INF;
    for(int i = 1; i <= N; i++) Y[++Y[0]] = V[i].s;
    Y[++Y[0]] = INF; sort(Y + 1, Y + Y[0] + 1);
    for(int i = 1; i <= Y[0]; i++)
    {
        X[i] = X[i - 1];
        if(Y[i] != Y[i - 1]) X[i]++;
    } maxim = X[Y[0]];
    for(int i = 1; i <= N; i++) V[i].s = X[lower_bound(Y + 1, Y + Y[0] + 1, V[i].s) - Y];
    for(int i = 1; i <= M; i++)
    {
        R[i].y1 = X[lower_bound(Y + 1, Y + Y[0] + 1, R[i].y1 - 1) - Y];
        R[i].y2 = X[lower_bound(Y + 1, Y + Y[0] + 1, R[i].y2) - Y];
    }
}

bool cmp(PUNCT a, PUNCT b)
{
    return a.X < b.X;
}

void adauga()
{
    for(int i = 1; i <= M; i++)
    {
        add.X = R[i].x1 - 1, add.Y = R[i].y1 - 1, add.ind = i, add.sign = 1;
        Q.pb(add);
        add.X = R[i].x2, add.Y = R[i].y2, add.ind = i, add.sign = 1;
        Q.pb(add);
        add.X = R[i].x2, add.Y = R[i].y1 - 1, add.ind = i, add.sign = -1;
        Q.pb(add);
        add.X = R[i].x1 - 1, add.Y = R[i].y2, add.ind = i, add.sign = -1;
        Q.pb(add);
    } sort(Q.begin(), Q.end(), cmp);
}

void update(int Y)
{
    for(int i = Y; i <= maxim; i += (i & (-i)))
        AIB[i]++;
}

int query(int Y)
{
    int rez = 0;
    for(int i = Y; i; i -= (i & (-i)))
        rez += AIB[i];
    return rez;
}

int main()
{
    citire();
    normalize();
    adauga();
    for(size_t i = 0, ind = 1; i < Q.size(); i++)
    {
        for(; V[ind].f <= Q[i].X && ind <= N; ind++)
            update(V[ind].s);
        ans[Q[i].ind] += Q[i].sign * query(Q[i].Y);
    }
    ofstream out("zoo.out");
    for(int i = 1; i <= M; i++) out<<ans[i]<<"\n";
    out.close();
    return 0;
}