Pagini recente » Cod sursa (job #1268024) | Cod sursa (job #715977) | Cod sursa (job #553747) | Cod sursa (job #1030584) | Cod sursa (job #3160972)
#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);
int matrix[1001][1001];
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;
if(Query[i].x2 > n)
Query[i].x2 = n;
if(Query[i].y1 > n)
Query[i].y1 = n;
if(Query[i].y2 > n)
Query[i].y2 = n;
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";
}
}