Pagini recente » Cod sursa (job #1655364) | Cod sursa (job #2692132) | Cod sursa (job #1015121) | Cod sursa (job #1536452) | Cod sursa (job #2618565)
#include <bits/stdc++.h>
#define maxn 200005
std::ofstream fout ("zoo.out");
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
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()
{
InParser fin ("zoo.in");
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;
}