Pagini recente » Cod sursa (job #78270) | Cod sursa (job #1527023) | Cod sursa (job #2838777) | Cod sursa (job #389123) | Cod sursa (job #2811322)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
const string fn = "file";
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser 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;
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();
if (a[p2].first > qrys[i].xf)p2--;
if (p2 == n + 1)
p2 = n;
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());
// cout << "\n";
// for (int i = 1; i <= n; ++i)
// cout << a[i].second << " ";
// cout << "\n\n\n";
// for (auto i : v)
// cout << i.p << " " << i.ys << " " << i.yf << " " << i.tip << " " << i.ind << "\n";
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;
}