Pagini recente » Cod sursa (job #2235968) | Cod sursa (job #536433) | Cod sursa (job #993432) | Cod sursa (job #1772593) | Cod sursa (job #2811331)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
const string fn = "file";
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int mxn = 16000;
const int mxm = 100000;
struct qr {
int xs, ys, xf, yf, i;
} qrys[mxm + 5];
struct nqr {
int p , ys, yf, ind, tip;
bool operator<(const nqr& oth) const {
if (p == oth.p)
return tip < oth.tip;
return p < oth.p;
}
};
vector<nqr> v;
unordered_map<int, int> mp;
int n, m;
int ans[mxm + 5];
vector<int> nrm;
vector<pair<int, int> > a;
int aib[mxn + 5];
void upd(int poz, int val) {
for (int i = poz; i <= n + 2 * m; i += (i & (-i)))
aib[i] += val;
}
int aibqry(int poz)
{
int ans = 0;
for (int i = poz; i >= 1; i -= (i & (-i)))
ans += aib[i];
return ans;
}
int qry2(int ys, int yf, int tip)
{
int ans1 = 0, ans2 = 0;
if (tip == 1)
{
ans1 = -aibqry(yf);
ans2 = aibqry(ys - 1);
}
else
{
ans1 = aibqry(yf);
ans2 = -aibqry(ys - 1);
}
return (ans1 + ans2);
}
int main() {
fin >> n;
a.resize(n + 1);
a[0] = { -2e9, -2e9};
for (int i = 1; i <= n; ++i) {
fin >> a[i].first >> a[i].second;
nrm.pb(a[i].second);
}
fin >> m;
for (int i = 1; i <= m; ++i)
{
fin >> qrys[i].xs >> qrys[i].ys >> qrys[i].xf >> qrys[i].yf;
qrys[i].i = i;
nrm.pb(qrys[i].ys);
nrm.pb(qrys[i].yf);
}
sort(nrm.begin(), nrm.end());
for (int i = 0; i < n + 2 * m; ++i) {
if (mp[nrm[i]] == 0)mp[nrm[i]] = i;
}
for (int i = 1; i <= n; ++i)
a[i].second = mp[a[i].second];
for (int i = 1; i <= m; ++i)
qrys[i].ys = mp[qrys[i].ys], qrys[i].yf = mp[qrys[i].yf];
sort(a.begin() + 1, a.end());
for (int i = 1; i <= m; ++i)
{
int p1, p2;
p1 = lower_bound(a.begin() + 1, a.end(), make_pair(qrys[i].xs, 0)) - a.begin();
p2 = upper_bound(a.begin() + 1, a.end(), make_pair(qrys[i].xf, 0)) - a.begin() - 1;
if (p2 < p1)
p2 = p1;
nqr x;
x.ys = qrys[i].ys;
x.yf = qrys[i].yf;
x.ind = i;
x.p = p1;
x.tip = 1;
v.pb(x);
x.p = p2;
x.tip = 2;
v.pb(x);
}
sort(v.begin(), v.end());
int j = 0;
bool tr = false;
for (int i = 1; i <= n; ++i)
{
tr = false;
while (j < m + m && v[j].p == i)
{
if (v[j].tip == 2 && !tr)
upd(a[i].second, + 1), tr = true;
ans[v[j].ind] += qry2(v[j].ys, v[j].yf, v[j].tip);
// cout << j << " " << qry2(v[j].ys, v[j].yf, v[j].tip) << '\n';
j++;
}
if (!tr) upd(a[i].second, + 1);
}
for (int i = 1; i <= m; ++i)
fout << ans[i] << '\n';
fin.close();
fout.close();
return 0;
}