Cod sursa(job #1517939)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 5 noiembrie 2015 00:29:14
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 16010;
const int MMAX = 100010;
const int NORMMAX = 220000;

struct query {int ind, x, y1, y2; bool isOne;} q[2 * MMAX]; //if !isOne, then it is four
struct point {int x, y;} v[NMAX];

int N, M;
int aib[NMAX];
vector<int> norm;
int ans[MMAX][4];

void updateAIB (int x, int val = 1) {
    while (x <= NORMMAX) {
        aib[x] += val;

        x += (x & (-x));
    }
}

int queryAIB (int pos) {
    int ans = 0;
    while (pos > 0) {
        ans += aib[pos];

        pos -= (pos & (-pos));
    }
    return ans;
}

bool critxq (query a, query b) {
    return a.x < b.x;
}

bool critxv (point a, point b) {
    return a.x < b.x;
}

int normval (int x) {
    return (lower_bound (norm.begin (), norm.end (), x) - norm.begin ());
}

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

    scanf ("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf ("%d%d", &v[i].x, &v[i].y);

        norm.push_back (v[i].y);
    }

    scanf ("%d", &M);
    for (int i = 1, j = 1; i <= M; i++, j += 2) {
        scanf ("%d%d%d%d", &q[j].x, &q[j].y1, &q[j + 1].x, &q[j + 1].y2);
        q[j].x--;
        q[j].y1--;

        q[j].ind = q[j + 1].ind = i;
        q[j].isOne = 1;
        q[j + 1].isOne = 0;

        q[j].y2 = q[j + 1].y2;
        q[j + 1].y1 = q[j].y1;

        norm.push_back (q[j].y1);
        norm.push_back (q[j].y2);
    }

    sort (norm.begin (), norm.end ());
    norm.erase (unique (norm.begin (), norm.end ()), norm.end ());

    sort (q + 1, q + 2 * M + 1, critxq);
    sort (v + 1, v + N + 1, critxv);

    int crt = 1;
    for (int i = 1; i <= 2 * M; i++) {
        while (crt <= N && v[crt].x <= q[i].x) {
            updateAIB (normval(v[crt].y) + 1);
            crt++;
        }

        if (q[i].isOne) {
            ans[q[i].ind][0] = queryAIB (normval(q[i].y1) + 1);
            ans[q[i].ind][1] = queryAIB (normval(q[i].y2) + 1);
        }
        else {
            ans[q[i].ind][2] = queryAIB (normval(q[i].y1) + 1);
            ans[q[i].ind][3] = queryAIB (normval(q[i].y2) + 1);
        }
    }

    for (int i = 1; i <= M; i++) {
        int ANS;
        ANS = ans[i][3] - ans[i][2] - ans[i][1] + ans[i][0];
        printf ("%d\n", ANS);
    }

    return 0;
}