Pagini recente » Cod sursa (job #389147) | Cod sursa (job #2510708) | Cod sursa (job #3149064) | Cod sursa (job #2550172) | Cod sursa (job #2831922)
/*
`-/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, ipos;
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;
}
};
vector <int> normalize_array (const vector <int> &v) {
vector <int> idx(v.size()), ret(v.size());
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&v](int i, int j) {
return v[i] < v[j];
});
ret[idx[0]] = 1;
for (size_t i = 1; i < v.size(); i++)
ret[idx[i]] = ret[idx[i - 1]] + (v[idx[i]] != v[idx[i - 1]]);
return ret;
}
void solve(int n, int m, const vector <Point> &v, vector <Query> &q) {
Fenwick aib(n + 2 * 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);
vector <int> vx, vy;
map <int, int> mpfirst, mpsecond;
for (int i = 0; i < n; i++) {
in >> v[i].x >> v[i].y;
v[i].type = 1; // punct
v[i].ipos = i;
vx.push_back(v[i].x);
vy.push_back(v[i].y);
}
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
vx.push_back(v[j].x); vx.push_back(v[j + 1].x);
vy.push_back(v[j].y); vy.push_back(v[j + 1].y);
v[j].qpos = v[j + 1].qpos = i;
v[j].ipos = j;
}
vx = normalize_array(vx);
vy = normalize_array(vy);
for (int i = 0; i < n + 2 * m; i++) {
v[i].x = vx[i];
v[i].y = vy[i];
}
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;
}