Cod sursa(job #2023566)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 19 septembrie 2017 09:33:14
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

#define Nmax 16005
#define Mmax 100005
#define LSB(x) ((x ^ (x - 1)) & x)

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

struct point
{
    int x,y;
};

struct event
{
    int t;
    int idx;
    int x, y1, y2;

};

event E[2 * Mmax];
point P[Nmax];

int ESIZE;
int N, M;
int ans[Mmax];
int normalize[2 * Mmax + Nmax + 55];
int aib[2 * Mmax + Nmax + 55];
int L;

bool qx(point a, point b)
{
    return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}

bool qxE(event a, event b)
{
    return a.x < b.x;
}

void update(int pos, int val)
{
    for(; pos <= L; pos += LSB(pos))
        aib[pos] += val;
}

int query(int pos)
{
    int ret = 0;
    for(; pos >= 1; pos -= LSB(pos))
        ret += aib[pos];
    return ret;
}

int main()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
        fin >> P[i].x >> P[i].y, normalize[++L] = P[i].y;
    fin >> M;
    for(int i = 1; i <= M; i++)
    {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        E[++ESIZE] = {-1, i, x1 - 1, y1, y2};
        E[++ESIZE] = {1, i, x2, y1, y2};
        normalize[++L] = y1;
        normalize[++L] = y2;
    }
    sort(normalize + 1, normalize + L + 1);
    int newL = 1;
    for(int i = 2; i <= L; i++)
        if(normalize[newL] != normalize[i])
            normalize[++newL] = normalize[i];
    L = newL;
    for(int i = 1; i <= N; i++)
        P[i].y = lower_bound(normalize + 1, normalize + L + 1, P[i].y) - normalize;
    for(int i = 1; i <= ESIZE; i++)
    {
        E[i].y1 = lower_bound(normalize + 1, normalize + L + 1, E[i].y1) - normalize;
        E[i].y2 = lower_bound(normalize + 1, normalize + L + 1, E[i].y2) - normalize;
    }
    sort(P + 1, P + N + 1, qx);
    sort(E + 1, E + ESIZE + 1, qxE);
    int j = 1;
    for(int i = 1; i <= ESIZE; i++)
    {
        for(; j <= N && P[j].x <= E[i].x; j++)
            update(P[j].y, 1);
        ans[E[i].idx] += E[i].t * (query(E[i].y2) - query(E[i].y1 - 1));
    }
    for(int i = 1; i <= M; i++)
        fout << ans[i] << "\n";
    return 0;
}