Cod sursa(job #1139998)

Utilizator darrenRares Buhai darren Data 11 martie 2014 17:40:05
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

void update(int now, int val)
{
    for (; now <= nowY; now += now & -now)
        AIB[now] += val;
}
int query(int now)
{
    int sum = 0;
    for (; now >= 1; now -= now & -now)
        sum += AIB[now];
    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()
{
    ifstream fin("zoo.in");
    ofstream fout("zoo.out");

    fin >> N;
    for (int i = 1; i <= N; ++i)
    {
        fin >> X[i] >> Y[i];
        yes[++yes[0]] = i;
        pos[i] = i;
    }

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

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

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

        int step, yw1 = -1, yw2 = -1;

        for (step = (1 << 14); step; step >>= 1)
            if (yw1 + step < int(Yn.size()) && Yn[yw1 + step] < yn1)
                yw1 += step;
        ++yw1;

        for (step = (1 << 14); step; step >>= 1)
            if (yw2 + step < int(Yn.size()) && Yn[yw2 + step] <= yn2)
                yw2 += step;

        if (yw1 > yw2) continue;

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

        V.push_back(make_pair(xn1 - 1, -i));
        V.push_back(make_pair(xn2, i));
    }

    sort(V.begin(), V.end());
    sort(pos + 1, pos + N + 1, compare);

    int now = 1;
    for (int i = 0; i < int(V.size()); ++i)
    {
        while (now <= N && X[pos[now]] <= V[i].first)
        {
            update(Y[pos[now]], 1);
            ++now;
        }

        if (V[i].second > 0)
            result[V[i].second] += query(Yw2[V[i].second]) - query(Yw1[V[i].second] - 1);
        else
            ;//result[-V[i].second] -= query(Yw2[-V[i].second]) - query(Yw1[-V[i].second] - 1);
    }

    for (int i = 1; i <= M; ++i)
        fout << result[i] << '\n';

    fin.close();
    fout.close();
}