Cod sursa(job #852695)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 11 ianuarie 2013 16:55:09
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 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, Y[(RMAX << 1) + MAX], AIB[(RMAX << 1) + 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()
{
    int n = 0;
    for(int i = 1; i <= N; i++) Y[++n] = V[i].s;
    for(int i = 1; i <= M; i++)
    {
        Y[++n] = R[i].y1;
        Y[++n] = R[i].y2;
    } sort(Y + 1, Y + n + 1);
    Y[0] = -INF; int i, j;
    for(i = 1, j = 0; i <= n; i++)
        if(Y[i] != Y[j]) Y[++j] = Y[i];
    maxim = j;
    for(int i = 1; i <= N; i++) V[i].s = lower_bound(Y + 1, Y + j + 1, V[i].s) - Y;
    for(int i = 1; i <= M; i++)
    {
        R[i].y1 = lower_bound(Y + 1, Y + j + 1, R[i].y1) - Y;
        R[i].y2 = lower_bound(Y + 1, Y + j + 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;
}