Cod sursa(job #1140082)

Utilizator darrenRares Buhai darren Data 11 martie 2014 18:40:01
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <cstdio>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("zoo.in");

char parse[1 << 20], *now;
inline void verify()
{
    if (*now == 0)
    {
        fin.get(parse, (1 << 20), '\0');
        now = parse;
    }
}
int get()
{
    while (*now != '-' && (*now < '0' || *now > '9'))
    {
        ++now;
        verify();
    }

    bool neg = false;
    if (*now == '-')
    {
        neg = true;
        ++now;
        verify();
    }

    int num = 0;
    while (*now >= '0' && *now <= '9')
    {
        num = num * 10 + (*now - '0');
        ++now;
        verify();
    }

    if (neg) num *= -1;

    return num;
}

int N, M;
int X[16002], Y[16002];
int Yw1[100002], Yw2[100002];
int yes[16002], nowY;
int Xn[160002], Yn[16002];
vector<int> V[16002];
int pos[16002];
int AIB[16002];
int result[100002];

void update(int pnow, int val)
{
    for (; pnow <= nowY; pnow += pnow & -pnow)
        AIB[pnow] += val;
}
int query(int pnow)
{
    int sum = 0;
    for (; pnow >= 1; pnow -= pnow & -pnow)
        sum += AIB[pnow];
    return sum;
}

bool compareY(const int& i1, const int& i2)
{
    return Y[i1] < Y[i2];
}
bool compare(const int& i1, const int& i2)
{
    return X[i1] < X[i2];
}

int main()
{
    freopen("zoo.out", "w", stdout);

    now = parse;
    verify();

    N = get();
    for (int i = 1; i <= N; ++i)
    {
        X[i] = get();
        Y[i] = get();
        Xn[i] = X[i];

        yes[++yes[0]] = i;
        pos[i] = i;
    }
    sort(Xn + 1, Xn + N + 1);

    sort(yes + 1, yes + yes[0] + 1, compareY);
    for (int i = 1; i <= yes[0]; ++i)
    {
        ++nowY;
        Yn[++Yn[0]] = Y[yes[i]];

        int ybase = Y[yes[i]];
        while (Y[yes[i]] == ybase)
        {
            Y[yes[i]] = nowY;
            ++i;
        }
        --i;
    }

    M = get();
    for (int i = 1, xn1, yn1, xn2, yn2; i <= M; ++i)
    {
        xn1 = get();
        yn1 = get();
        xn2 = get();
        yn2 = get();

        int step, yw1 = 0, yw2 = 0;

        for (step = (1 << 13); step; step >>= 1)
            if (yw1 + step <= Yn[0] && Yn[yw1 + step] < yn1)
                yw1 += step;
        ++yw1;

        for (step = (1 << 13); step; step >>= 1)
            if (yw2 + step <= Yn[0] && Yn[yw2 + step] <= yn2)
                yw2 += step;

        if (yw1 > yw2) continue;

        Yw1[i] = yw1;
        Yw2[i] = yw2;

        int xw1 = 0, xw2 = 0;
        for (step = (1 << 13); step; step >>= 1)
            if (xw1 + step <= N && Xn[xw1 + step] < xn1)
                xw1 += step;

        for (step = (1 << 13); step; step >>= 1)
            if (xw2 + step <= N && Xn[xw2 + step] <= xn2)
                xw2 += step;

        V[xw1].push_back(-i);
        V[xw2].push_back(i);
    }

    sort(pos + 1, pos + N + 1, compare);

    for (int i = 1; i <= N; ++i)
    {
        int xnow = X[pos[i]];
        while (X[pos[i]] == xnow)
        {
            update(Y[pos[i]], 1);
            ++i;
        }
        --i;

        for (int j = 0; j < int(V[i].size()); ++j)
        {
            if (V[i][j] > 0)
                result[V[i][j]] += query(Yw2[V[i][j]]) - query(Yw1[V[i][j]] - 1);
            else
                result[-V[i][j]] -= query(Yw2[-V[i][j]]) - query(Yw1[-V[i][j]] - 1);
        }
    }

    for (int i = 1; i <= M; ++i)
        printf("%d\n", result[i]);

    fin.close();
}