Pagini recente » Cod sursa (job #1287240) | Cod sursa (job #1297357) | Cod sursa (job #1869070) | Cod sursa (job #2308558) | Cod sursa (job #3306064)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n, tt;
pair<int, int> v[16010];
vector<int> aux;
int maxLin, maxCol;
vector<vector<int>> aib;
inline void update(int x, int y, int val) {
for(int i=x; i<=maxLin; i+=(i&(-i)))
for(int j=y; j<=maxCol; j+=(j&(-j))) aib[i][j] += val;
}
inline int query(int x, int y) {
int rez = 0;
for(int i=x; i>=1; i-=(i&(-i)))
for(int j=y; j>=1; j-=(j&(-j))) rez += aib[i][j];
return rez;
}
inline int querySubmatrice(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=1; i<=n; i++) {
fin >> v[i].first >> v[i].second;
aux.push_back(v[i].first);
aux.push_back(v[i].second);
}
sort(aux.begin(), aux.end());
vector<int>::iterator it = unique(aux.begin(), aux.end());
aux.resize(distance(aux.begin(), it));
for(int i=1; i<=n; i++) {
v[i].first = lower_bound(aux.begin(), aux.end(), v[i].first) - aux.begin() + 1;
v[i].second = lower_bound(aux.begin(), aux.end(), v[i].second) - aux.begin() + 1;
maxLin = max(maxLin, v[i].first);
maxCol = max(maxCol, v[i].second);
}
aib.resize(maxLin + 1);
for(int i=0; i<=maxLin; i++) aib[i].resize(maxCol + 1);
for(int i=1; i<=n; i++) update(v[i].first, v[i].second, 1);
fin >> tt;
while(tt--) {
int x1, y1, x2, y2; fin >> x1 >> y1 >> x2 >> y2;
if(x1 > maxLin) x1 = maxLin;
else x1 = lower_bound(aux.begin(), aux.end(), x1) - aux.begin() + 1;
if(y1 > maxCol) y1 = maxCol;
else y1 = lower_bound(aux.begin(), aux.end(), y1) - aux.begin() + 1;
if(x2 > maxLin) x2 = maxLin;
else x2 = lower_bound(aux.begin(), aux.end(), x2) - aux.begin() + 1;
if(y2 > maxCol) y2 = maxCol;
else y2 = lower_bound(aux.begin(), aux.end(), y2) - aux.begin() + 1;
fout << querySubmatrice(x1, y1, x2, y2) << '\n';
}
return 0;
}