Pagini recente » Cod sursa (job #1510098) | Cod sursa (job #1238514) | Cod sursa (job #624540) | Cod sursa (job #2136345) | Cod sursa (job #995721)
Cod sursa(job #995721)
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 16010
using namespace std;
struct Punct
{
int x, y;
bool operator <(const Punct &A) const
{
return x < A.x;
}
};
Punct a[NMAX];
int px[NMAX];
vector <int> aint[4*NMAX];
int p, q, n, m;
int X1, X2, Y1, Y2, sol;
inline void BuildTree(const int node, const int st, const int dr)
{
if (st == dr)
{
aint[node].push_back(a[st].y);
return ;
}
int mij = (st+dr) >> 1;
BuildTree(node*2, st, mij);
BuildTree(node*2+1, mij+1, dr);
aint[node].resize(aint[2*node].size() + aint[2*node+1].size());
merge(aint[2*node].begin(), aint[2*node].end(), aint[2*node+1].begin(), aint[2*node+1].end(), aint[node].begin());
}
inline void Query(const int node, const int st, const int dr)
{
if (p <= st && dr <= q)
{
sol += upper_bound(aint[node].begin(), aint[node].end(), Y2) - lower_bound(aint[node].begin(), aint[node].end(), Y1);
return;
}
int mij = (st+dr)>>1;
if (p <= mij)
Query(node*2, st, mij);
if (mij < q)
Query(node*2+1, mij+1, dr);
}
int main()
{
ifstream f ("zoo.in");
ofstream g ("zoo.out");
f>>n;
int i;
for (i=1; i<=n; ++i)
{
f>>a[i].x>>a[i].y;
px[i] = a[i].x;
}
sort(a+1, a+n+1);
sort(px+1, px+n+1);
BuildTree(1, 1, n);
f>>m;
while (m--)
{
f>>X1>>Y1>>X2>>Y2;
if (X2 < px[1] || X1 > px[n])
g<<"0\n";
else
{
sol = 0;
p = lower_bound(px+1, px+n+1, X1) - px;
q = upper_bound(px+1, px+n+1, X2) - px - 1;
Query(1, 1, n);
g<<sol<<"\n";
}
}
f.close();
g.close();
return 0;
}