Cod sursa(job #2908024)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 1 iunie 2022 10:10:31
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>
#define fi first
#define se second
#define z(x) ((x)&(-x))
using namespace std;
int const N = 16003;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n , q , a , b , c , d;
int X[N];
vector<int> t[N];
pair<int , int> p[N];
void add(int idx , int val){
    for(int i = idx ; i <= n ; i += z(i))
        t[i].push_back(val);
}
int sum(int p , int st , int dr){
    int ans = 0;
    for(int i = p ; i ; i -= z(i))
        ans += (upper_bound(t[i].begin() , t[i].end() , dr) - lower_bound(t[i].begin() , t[i].end() , st));
    return ans;
}
int query(int from , int to , int st , int dr){
    return sum(to , st , dr) - sum(from - 1 , st , dr);
}
int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; ++ i){
        fin >> p[i].fi >> p[i].se;
        X[i] = p[i].fi;
    }
    sort(p + 1 , p + 1 + n);
    sort(X + 1 , X + 1 + n);
    for(int i = 1 ; i <= n ; ++ i)
        add(i , p[i].se);
    for(int i = 1 ; i <= n ; ++ i)
        sort(t[i].begin() , t[i].end());
    fin >> q;
    for(int i = 1 ; i <= q ; ++ i){
        fin >> a >> b >> c >> d;
        int x1 = (lower_bound(X + 1 , X + 1 + n , a) - X);
        int x2 = (upper_bound(X + 1 , X + 1 + n , c) - X);
        fout << query(x1 , x2 - 1 , b , d) << '\n';
    }
    return 0;
}