Pagini recente » Cod sursa (job #2772494) | Cod sursa (job #1309188) | Cod sursa (job #589676) | Cod sursa (job #10611) | Cod sursa (job #2618562)
#include <bits/stdc++.h>
#define maxn 200005
std::ifstream fin ("zoo.in");
std::ofstream fout ("zoo.out");
struct str{
int x, y, type, index;
};
std::vector <str> arr;
bool sort_cond (str a, str b){
if (a.y != b.y) return a.y < b.y;
return a.type > b.type;
}
bool sort_X (str a, str b){
return a.x < b.x;
}
bool sort_Y (str a, str b){
return a.y < b.y;
}
int bit[maxn];
void update (int pos, int val){
while (pos < maxn){
bit[pos] += val;
pos = (pos | (pos+1));
}
}
int query (int pos){
int ans = 0;
while (pos >= 0){
ans += bit[pos];
pos = (pos & (pos+1)) - 1;
}
return ans;
}
int ans[maxn];
int main()
{
int n, i, Q;
int x1, y1, x2, y2;
int cnt, last;
fin >> n;
for (i=0; i<n; i++){
fin >> x1 >> y1;
arr.push_back ({x1, y1, 2, i});
}
fin >> Q;
for (i=0; i<Q; i++){
fin >> x1 >> y1 >> x2 >> y2;
arr.push_back ({x2, y2, 1, i});
arr.push_back ({x1-1, y1-1, 1, i});
arr.push_back ({x2, y1-1, -1, i});
arr.push_back ({x1-1, y2, -1, i});
}
std::sort (arr.begin(), arr.end(), sort_X);
for (i=0, last=-2000000005, cnt=-1; i<arr.size(); i++){
if (arr[i].x != last){
cnt ++;
last = arr[i].x;
}
arr[i].x = cnt;
}
//for (i=0; i<arr.size(); i++)
// fout << arr[i].x << ' ' << arr[i].y << ' ' << arr[i].type << ' ' << arr[i].index << '\n';
std::sort (arr.begin(), arr.end(), sort_cond);
for (i=0, last=-2000000005, cnt=-1; i<arr.size(); i++){
if (arr[i].y != last){
cnt ++;
last = arr[i].y;
}
arr[i].y = cnt;
}
int my = cnt;
for (int y=0, i=0; y<=my; y++){
for (;arr[i].y == y and i < arr.size(); i++){
if (arr[i].type == 2)
update (arr[i].x, 1);
else
ans[arr[i].index] += arr[i].type * query (arr[i].x);
}
}
for (i=0; i<Q; i++)
fout << ans[i] << '\n';
return 0;
}