Cod sursa(job #2758817)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 13 iunie 2021 02:36:43
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
/*
    Sursa foarte experimentala
*/

#include <iostream>
#include <fstream>
#include <algorithm>

#define NMAX 16000 //saispe mii
#define MMAX 100000 //o suta de mii

using namespace std;

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

int N;
int NX, NY;
int * aib;
int distX[NMAX], distY[NMAX];

struct element{
    int val;
    int poz;
}x[NMAX], y[NMAX];

int comparare(element A, element B){
    return A.val < B.val;
}

struct puncte{
    int x, y;
}v[NMAX];

void updateAIB2d(int x, int y, int val){
    for(int j = x; j <= NX; j += j & (-j)){
        for(int i = y; i <= NY; i += i & (-i)){

            int k = i - 1;
            int z = j - 1;

            //aib[x][y] += val;
            *(aib + k * NX + z) += val;
        }
    }
}

inline int lower(element v[], int val, int st, int dr){
    //il vreau pe cel mai mare din sir cu conditia sa fie mai mic sau egal cu val

    int lo = st - 1;
    int hi = dr + 1;

    while(hi - lo > 1){
        int mid = lo + (hi - lo) / 2;

        if(v[mid].val <= val){
            lo = mid;
        }
        else {
            hi = mid;
        }
    }

    if(lo == st - 1){
        return -1;
    }

    return lo;
}

inline int upper(element v[], int val, int st, int dr){
    //il vreau pe cel mai mic din sir cu conditia sa fie mai mare sau egal cu val

    int lo = st - 1;
    int hi = dr + 1;

    while(hi - lo > 1){
        int mid = lo + (hi - lo) / 2;

        if(v[mid].val >= val){
            hi = mid;
        }
        else {
            lo = mid;
        }
    }

    if(hi == dr + 1){
        return -1;
    }

    return hi;
}


int query(int x, int y){
    //printf("x = %d\ny = %d\n\n", x, y);

    int rsp = 0;
    for(int j = x; j >= 1; j -= j & (-j)){
        //printf("j = %d\n", j);
        for(int i = y; i >= 1; i -= i & (-i)){
            //printf("i = %d\n", i);
            int k = i - 1;
            int z = j - 1;


            //rsp += aib[i - 1][j - 1];
            rsp += * (aib + k * NX + z);
        }
    }

    return rsp;
}

inline int queryAIB2d(int x1, int y1, int x2, int y2){
    return
    query(x2, y2)
    -
    query(x2, y1 - 1)
    -
    query(x1 - 1, y2)
    +
    query(x1 - 1, y1 - 1);
}

int main()
{
    fin >> N;

    for(int i = 0; i < N; i++){
        fin >> x[i].val >> y[i].val;
        x[i].poz = i;
        y[i].poz = i;
    }

    sort(x, x + N, comparare);
    sort(y, y + N, comparare);

    distX[0] = 1;
    distY[0] = 1;
    for(int i = 0; i < N; i++){
        if(i > 0){
            if(x[i].val != x[i - 1].val){
                distX[i] = distX[i - 1] + 1;
            }
            else {
                distX[i] = distX[i - 1];
            }
        }

        if(i > 0){
            if(y[i].val != y[i - 1].val){
                distY[i] = distY[i - 1] + 1;
            }
            else {
                distY[i] = distY[i - 1];
            }
        }

        v[ x[i].poz ].x = distX[i];
        v[ y[i].poz ].y = distY[i];
    }


    NX = distX[N - 1];
    NY = distY[N - 1];

    aib = (int *) calloc( NX * NY, sizeof(int) );

    for(int i = 0; i < N; i++){
        updateAIB2d(v[i].x, v[i].y, 1);
    }


    int M;
    fin >> M;

    for(int i = N; i < N + M; i++){
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        x1 = upper(x, x1, 0, N - 1);
        y1 = upper(y, y1, 0, N - 1);
        x2 = lower(x, x2, 0, N - 1);
        y2 = lower(y, y2, 0, N - 1);

        if(x1 == -1 || y1 == -1 || x2 == -1 || y2 == -1){
            fout << 0 << "\n";
        }
        else {
            fout << queryAIB2d(distX[ x1 ], distY[ y1 ], distX[ x2 ], distY[ y2 ]) << "\n";
        }
    }

    return 0;

}