Cod sursa(job #852735)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 11 ianuarie 2013 17:51:22
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 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, Q[RMAX << 2];


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

int BS(int X, int *V, bool T)
{
    int i =0, pas = 1 << 18;
    for(i = 0; pas; pas >>= 1)
        if(i + pas <= V[0] && V[i + pas] < X) i += pas;
    if(!T) return i;
    if(V[i + 1] == X) return i + 1;
    return i;
}

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[BS(V[i].s, Y, 1)];
    for(int i = 1; i <= M; i++)
    {
        R[i].y1 = X[BS(R[i].y1, Y, 0)];
        R[i].y2 = X[BS(R[i].y2, Y, 1)];
    }
}

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, add.ind = i, add.sign = 1;
        Q[(i - 1) * 4 + 1] = add;
        add.X = R[i].x2, add.Y = R[i].y2, add.ind = i, add.sign = 1;
        Q[(i - 1) * 4 + 2] = add;
        add.X = R[i].x2, add.Y = R[i].y1, add.ind = i, add.sign = -1;
        Q[(i - 1) * 4 + 3] = add;
        add.X = R[i].x1 - 1, add.Y = R[i].y2, add.ind = i, add.sign = -1;
        Q[(i - 1) * 4 + 4] = add;
    } sort(Q + 1, Q + 4 * M + 1, 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(int i = 1, ind = 1, A = 4 * M; i <= A; 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;
}