Cod sursa(job #3160978)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 25 octombrie 2023 12:49:44
Problema Zoo Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>
#define DIM 16001

using namespace std;

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

struct q{

    int x1, y1, x2, y2;


};

q Query[10 * DIM];

vector < unordered_map <int, int> > matrix(DIM);

pair <int, int> point[DIM];

map <int, bool> ok;

map <int, bool> :: iterator it;

unordered_map <int, int> answer;

int n, i, j, Q, f;

int lsb(int n){

    return (n & -n);

}

void Update(int i, int j){

    for(int lin = i; lin <= n ; lin += lsb(lin))
        for(int col = j ; col <= n ; col += lsb(col))
            matrix[lin][col]++;


}

int query(int i, int j){

    int answer = 0;

    for(int lin = i; lin ; lin -= lsb(lin))
        for(int col = j; col ; col -= lsb(col))
            answer += matrix[lin][col];

    return answer;

}

int main(){

    fin >> n;

    for(i=1;i<=n;i++){

        fin >> point[i].first >> point[i].second;

        ok[point[i].first] = 1;

        ok[point[i].second] = 1;

    }

    fin >> Q;

    for(i=1;i<=n;i++){

        fin >> Query[i].x1 >> Query[i].y1 >> Query[i].x2 >> Query[i].y2;

        ok[Query[i].x1] = 1;

        ok[Query[i].y1] = 1;

        ok[Query[i].x2] = 1;

        ok[Query[i].y2] = 1;

    }

    for(it = ok.begin(); it != ok.end(); it++)
        answer[it -> first] = ++f;

    for(i=1;i<=n;i++){

        point[i].first = answer[point[i].first];

        point[i].second = answer[point[i].second];

        Update(point[i].first, point[i].second);

    }

    for(i=1;i<=Q;i++){

        Query[i].x1 = answer[Query[i].x1];

        Query[i].x2 = answer[Query[i].x2];

        Query[i].y1 = answer[Query[i].y1];

        Query[i].y2 = answer[Query[i].y2];

        if(Query[i].x1 > n)
            Query[i].x1 = n + 1;

        if(Query[i].x2 > n)
            Query[i].x2 = n + 1;

        if(Query[i].y1 > n)
            Query[i].y1 = n + 1;

        if(Query[i].y2 > n)
            Query[i].y2 = n + 1;

        fout << query(Query[i].x1 - 1, Query[i].y1 - 1) - query(Query[i].x1 - 1, Query[i].y2) - query(Query[i].x2, Query[i].y1 - 1) + query(Query[i].x2, Query[i].y2) << "\n";


    }



}