Pagini recente » Cod sursa (job #1387263) | Cod sursa (job #2371928) | Cod sursa (job #2173374) | Cod sursa (job #803793) | Cod sursa (job #3341885)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int NMAX = 16'000;
const int MMAX = 1e5;
int n, m, ID, ind;
map<int, int> mp;
int answer[MMAX + 1];
struct Event {
int type, x, y1, y2, qind;
bool operator < (const Event& other) const {
if(x != other.x) {
return x < other.x;
}
return type < other.type;
}
}events[3 * MMAX + 1];
struct AIB {
int n;
int aib[3 * MMAX + 1];
void init(int n) {
this->n = n;
fill(aib + 1, aib + n + 1, 0);
}
void update(int pos, int value) {
for(int i = pos; i <= n; i += i & (-i)) {
aib[i] += value;
}
}
int query(int pos) {
int answer = 0;
for(int i = pos; i >= 1; i -= i & (-i)) {
answer += aib[i];
}
return answer;
}
}aib;
int main() {
fin >> n;
for(int i = 1; i <= n; i++) {
int x, y;
fin >> x >> y;
mp[y] = 1;
events[++ind] = {0, x, y, y, 0};
}
fin >> m;
for(int i = 1; i <= m; i++) {
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
mp[y1] = 1;
mp[y2] = 1;
events[++ind] = {1, x2, y1, y2, i};
events[++ind] = {2, x1 - 1, y1, y2, i};
}
for(auto& x : mp) {
x.second = ++ID;
}
sort(events + 1, events + ind + 1);
aib.init(ID);
for(int i = 1; i <= ind; i++) {
auto [type, x, y1, y2, qind] = events[i];
y1 = mp[y1];
y2 = mp[y2];
if(type == 0) {
aib.update(y1, 1);
}
else {
int sign = (type == 1 ? 1 : -1);
answer[qind] += (aib.query(y2) - aib.query(y1 - 1)) * sign;
}
}
for(int i = 1; i <= m; i++) {
fout << answer[i] << '\n';
}
return 0;
}