Pagini recente » Cod sursa (job #349989) | Cod sursa (job #321276) | Cod sursa (job #966568) | Cod sursa (job #528969) | Cod sursa (job #2831224)
/*
`-/oo+/- ``
.oyhhhhhhyo.`od
+hhhhyyoooos. h/
+hhyso++oosy- /s
.yoooossyyo:``-y`
..----.` ``.-/+:.`
`````..-::/.
`..```.-::///`
`-.....--::::/:
`.......--::////:
`...`....---:::://:
`......``..--:::::///:`
`---.......--:::::////+/`
----------::::::/::///++:
----:---:::::///////////:`
.----::::::////////////:-`
`----::::::::::/::::::::-
`.-----:::::::::::::::-
...----:::::::::/:-`
`.---::/+osss+:`
``.:://///-.
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '
using namespace std;
ifstream in ("zoo.in");
ofstream out ("zoo.out");
const int INF = 2e9;
struct Point {
int x, y, type, qpos;
bool operator < (const Point aux) const {
if (x == aux.x) {
if (y == aux.y)
return type < aux.type;
return y < aux.y;
}
return x < aux.x;
}
};
struct Query {
pair <int, int> st_jos, dr_sus;
int st_jos_ans, dr_sus_ans;
};
class Fenwick {
private:
vector <int> a;
int _n;
int lsb(int i) {
return (i & (-i));
}
public:
Fenwick(int n) {
a.resize(1 + n);
_n = n;
}
void Update(int pos) {
for (int i = pos; i <= _n; i += lsb(i))
a[i]++;
}
int Query(int pos) {
int ans = 0;
for (int i = pos; i > 0; i -= lsb(i))
ans += a[i];
return ans;
}
};
void solve(int n, int m, const vector <Point> &v, vector <Query> &q) {
Fenwick aib(n + m + 2);
for (auto it : v) {
//debugsp(it.x); debugsp(it.y); debug(it.type);
if (it.type == 1)
aib.Update(it.y);
else {
//debug(it.qpos);
int l, r;
l = it.y;
if (it.type == 0)
r = q[it.qpos].dr_sus.second;
else r = q[it.qpos].st_jos.second;
if (l > r)
swap(l, r);
//debugsp(l); debug(r);
if (it.type == 0)
q[it.qpos].st_jos_ans = aib.Query(r) - aib.Query(l - 1);
else
q[it.qpos].dr_sus_ans = aib.Query(r) - aib.Query(l - 1);
}
}
}
int main() {
int n, m;
in >> n;
vector <Point> v(n);
map <int, int> mpfirst, mpsecond;
for (int i = 0; i < n; i++) {
in >> v[i].x >> v[i].y;
v[i].type = 1; // punct
mpfirst.insert(make_pair(v[i].x, 0));
mpsecond.insert(make_pair(v[i].y, 0));
}
in >> m;
v.resize(n + 2 * m);
vector <Query> q(m);
for (int i = 0; i < m; i++) {
int j = 2 * i + n;
in >> v[j].x >> v[j].y; v[j].type = 0; // st_jos
in >> v[j + 1].x >> v[j + 1].y; v[j + 1].type = 2; // dr_sus
v[j].qpos = v[j + 1].qpos = i;
mpfirst.insert(make_pair(v[j].x, 0));
mpfirst.insert(make_pair(v[j + 1].x, 0));
mpsecond.insert(make_pair(v[j].y, 0));
mpsecond.insert(make_pair(v[j + 1].y, 0));
}
int cnt = 0;
for (auto &it : mpfirst)
it.second = ++cnt;
cnt = 0;
for (auto &it : mpsecond)
it.second = ++cnt;
for (auto &it : v) {
it.x = mpfirst[it.x];
it.y = mpsecond[it.y];
}
for (int i = 0; i < m; i++) {
int j = 2 * i + n;
q[i].st_jos = make_pair(v[j].x, v[j].y);
q[i].dr_sus = make_pair(v[j + 1].x, v[j + 1].y);
}
//for (auto it : v)
// cerr << it.x << ' ' << it.y << '\n';
sort(v.begin(), v.end());
solve(n, m, v, q);
for (auto it : q)
out << it.dr_sus_ans - it.st_jos_ans << '\n';
in.close();
out.close();
return 0;
}