Cod sursa(job #2758676)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 11 iunie 2021 23:57:30
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 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 aib[NMAX + 1][NMAX + 1];
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 <= N; j += j & (-j)){
        for(int i = y; i <= N; i += i & (-i)){
            aib[i][j] += 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);
            rsp += aib[i][j];
        }
    }

    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];
    }

    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";
        }
    }

}