Pagini recente » Cod sursa (job #640730) | Cod sursa (job #2117008) | Cod sursa (job #929418) | Istoria paginii runda/onis-2014-runda-2/clasament | Cod sursa (job #833168)
Cod sursa(job #833168)
#include <fstream>
#include <vector>
#define NMAX (1<<20)
using namespace std;
int n,m,nr,p;
struct punct
{
int x,y;
};
punct a[16010],c1,c2;
vector <int> v[NMAX];
ifstream in("zoo.in");
ofstream out("zoo.out");
void scan()
{
in>>n;
for (int i=1;i<=n;i++)
{
in>>a[i].x>>a[i].y;
}
in>>m;
}
int part(int st, int dr)
{
punct p,aux;
int i,j;
i=st-1;
j=dr+1;
p=a[(st+dr)/2];
while (1)
{
do{i++;}while (a[i].x<p.x || (a[i].x==p.x && a[i].y<p.y));
do{j--;}while (p.x<a[j].x || (a[j].x==p.x && p.y<a[j].y));
if (i<j)
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
}
else return j;
}
}
void quicks(int st,int dr)
{
int p;
if (st<dr)
{
p=part(st,dr);
quicks(st,p);
quicks(p+1,dr);
}
}
void merge(int k,int a,int b)
{
int i=0,j=0;
while (i<v[a].size() && j<v[b].size())
{
if (v[a][i]<v[b][j])
{
v[k].push_back(v[a][i]);
i++;
}
else
{
v[k].push_back(v[b][j]);
j++;
}
}
while (i<v[a].size())
{
v[k].push_back(v[a][i]);
i++;
}
while (j<v[b].size())
{
v[k].push_back(v[b][j]);
j++;
}
}
void constructTree(int k,int st,int dr)
{
if (st==dr)
{
while (p<=n && a[p].x==a[st].x)
{
v[k].push_back(a[p].y);
p++;
}
return;
}
int mij;
mij=(st+dr)/2;
constructTree(2*k,st,mij);
constructTree(2*k+1,mij+1,dr);
merge(k,2*k,2*k+1);
}
int cautbin(int k,int val)
{
int i, step;
for (step = 1; step < v[k].size(); step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < v[k].size()&& v[k][i + step] < val)
i += step;
return i;
}
void query(int k,int st,int dr)
{
int k1,k2;
if (st>dr)
return;
if (c1.x<=a[st].x && a[dr].x<=c2.x)
{
k1=cautbin(k,c1.y);
k2=cautbin(k,c2.y+1);
nr=nr+k2-k1+1;
return;
}
int mij;
mij=(st+dr)/2;
if (st==dr)
return;
if (c1.x<=a[mij].x)
query(2*k,st,mij);
if (a[mij].x<c2.x)
query(2*k+1,mij+1,dr);
}
void solve()
{
for (int i=1;i<=m;i++)
{
nr=0;
in>>c1.x>>c1.y>>c2.x>>c2.y;
if (!(a[1].x>c2.x || a[n].x<c1.x))
query(1,1,n);
out<<nr<<"\n";
}
}
int main()
{
p=1;
scan();
quicks(1,n);
constructTree(1,1,n);
solve();
return 0;
}