Pagini recente » Cod sursa (job #1993976) | Cod sursa (job #754109) | Cod sursa (job #2339482) | Cod sursa (job #1103735) | Cod sursa (job #3307609)
// NAME: zoo
// SOURCE: .compion 2003
// URL: https://www.infoarena.ro/problema/zoo
// Normalize points, and do a vertical scanline + BIT
#include <algorithm>
#include <stdio.h>
#include <utility>
#include <vector>
#define MAXN 16'001
#define MAXM 100'001
struct Point {
int x;
int y;
} animale[MAXN];
struct dreptunghi {
int i;
int j;
int l;
int c;
} submat[MAXM];
std::vector<std::pair<int, int>> norm;
struct Query {
enum OP { CLOSE, OPEN } op;
int id;
};
struct Event {
enum TYPE { POINT = 0, DREPT = 1 } type;
int y;
union {
int x;
Query query;
};
};
std::vector<Event> ev;
int ans[MAXM];
int n, m;
struct Fenwick {
int aib[MAXN + 1];
void update(int pos, int val) {
pos++; // indexed starting with 1
while (pos <= n) {
aib[pos] += val;
pos += (pos & (-pos));
}
}
int query(int pos) {
if (pos < 0)
return 0;
pos++;
int sum = 0;
while (pos) {
sum += aib[pos];
pos -= (pos & (-pos));
}
return sum;
}
int query(int st, int dr) { return query(dr) - query(st - 1); }
};
Fenwick aib;
int cautbinLower(int pos) {
int s = -1;
int d = norm.size()-1;
while (d - s > 1) {
int m = (s + d) / 2;
if (norm[m].first < pos)
s = m;
else
d = m;
}
if(norm[d].first < pos)
return -1;
return norm[d].second;
}
int cautbinUpper(int pos) {
int s = -1;
int d = norm.size();
while (d - s > 1) {
int m = (s + d) / 2;
if (norm[m].first > pos)
d = m;
else
s = m;
}
if(s==-1)
return -1;
return norm[s].second;
}
int main() {
freopen("zoo.in", "r", stdin);
freopen("zoo.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &animale[i].y, &animale[i].x);
}
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d%d%d%d", &submat[i].i, &submat[i].j, &submat[i].l, &submat[i].c);
}
std::sort(animale, animale + n, [](Point &a, Point &b) { return a.x < b.x; });
for (int i = 0; i < n; i++) {
norm.push_back(std::make_pair(animale[i].x, i));
ev.push_back(
{.type = Event::TYPE::POINT, .y = animale[i].y, .x = i});
}
for (int i = 0; i < m; i++) {
ev.push_back({.type = Event::TYPE::DREPT,
.y = submat[i].i,
.query = {.op = Query::OP::OPEN, .id = i}});
ev.push_back({.type = Event::TYPE::DREPT,
.y = submat[i].l,
.query = {.op = Query::OP::CLOSE, .id = i}});
}
std::sort(ev.begin(), ev.end(), [](Event &a, Event &b) -> bool {
if (a.y != b.y)
return a.y < b.y;
if ((a.type == Event::TYPE::DREPT && a.query.op == Query::CLOSE) ||
(b.type == Event::TYPE::DREPT && b.query.op == Query::CLOSE))
return a.type < b.type;
else
return a.type > b.type;
});
for (auto e : ev) {
if (e.type == Event::TYPE::POINT) {
aib.update(e.x, 1);
} else {
int x1 = cautbinLower(submat[e.query.id].j);
int x2 = cautbinUpper(submat[e.query.id].c);
if (e.query.op == Query::OP::OPEN)
ans[e.query.id] -= aib.query(x1, x2);
else
ans[e.query.id] += aib.query(x1, x2);
}
}
for (int i = 0; i < m; i++) {
printf("%d\n", ans[i]);
}
return 0;
}