Pagini recente » Cod sursa (job #135690) | Cod sursa (job #2963) | Cod sursa (job #2770279) | Cod sursa (job #13387) | Cod sursa (job #3133715)
#include <bits/stdc++.h>
#define L 16005
#define lsb(x) ((x ^ (x - 1)) & x)
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n, m;
pair <int, int> a[L];
vector <int> t[L];
int X[L];
void add(int ind, int val){
for (int i = ind; i <= n; i += lsb(i))
t[i].push_back(val);
}
int sum(int p, int st, int dr){
int ret = 0;
for (int i = p; i; i -= lsb(i))
ret += (upper_bound(t[i].begin(), t[i].end(), dr) - lower_bound(t[i].begin(), t[i].end(), st));
return ret;
}
int query(int le, int ri, int st, int dr){
return sum(ri, st, dr) - sum(le - 1, st, dr);
}
int main(){
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].first >> a[i].second;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
add(i, a[i].second);
for (int i = 1; i <= n; i++)
sort(t[i].begin(), t[i].end());
for (int i = 1; i <= n; i++)
X[i] = a[i].first;
fin >> m;
for (int i = 1; i <= m; i++){
int x, y, xx, yy;
fin >> x >> y >> xx >> yy;
int x1 = lower_bound(X + 1, X + 1 + n, x) - X;
int x2 = upper_bound(X + 1, X + 1 + n, xx) - X;
fout << query(x1, x2 - 1, y, yy) << "\n";
}
return 0;
}