Pagini recente » Cod sursa (job #44694) | Cod sursa (job #186354) | Cod sursa (job #1450028) | Cod sursa (job #222172) | Cod sursa (job #996113)
Cod sursa(job #996113)
#include<fstream>
#include<vector>
#include<algorithm>
#include<map>
#define NMAX 16005
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n,m,sol,a,b,c,d;
vector<int> AINT[4*NMAX],vals[NMAX];
pair<int,int> v[NMAX];
map<int,int> M;
map<int,int>::iterator it;
bool cmp(const int a,const int b)
{
return a<b;
}
void update(int left,int right,int nod)
{
if(left==right)
{
AINT[nod]=vals[left];
return;
}
int middle=(left+right)/2;
update(left,middle,2*nod);
update(middle+1,right,2*nod+1);
AINT[nod].resize(AINT[2*nod].size()+AINT[2*nod+1].size());
merge(AINT[2*nod].begin(),AINT[2*nod].end(),AINT[2*nod+1].begin(),AINT[2*nod+1].end(),AINT[nod].begin(),cmp);
}
void query(int left,int right,int nod)
{
if(left>c || right<a)
return;
if(a<=left && right<=c)
{
sol+=(int)(upper_bound(AINT[nod].begin(),AINT[nod].end(),d)-upper_bound(AINT[nod].begin(),AINT[nod].end(),b-1));
return;
}
int middle=(left+right)/2;
query(left,middle,2*nod);
query(middle+1,right,2*nod+1);
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].first>>v[i].second;
sort(v+1,v+n+1);
for(int i=1,j=0;i<=n;i++)
if(M.find(v[i].first)==M.end())
M.insert(make_pair(v[i].first,++j));
it=M.begin();
for(int i=1,poz;i<=n;i++,it++)
{
poz=it->second;
for(;v[i].first==it->first && i<=n;i++)
vals[poz].push_back(v[i].second);
i--;
}
n=M.size();
update(1,n,1);
fin>>m;
while(m--)
{
sol=0;
fin>>a>>b>>c>>d;
it=M.upper_bound(a-1);
if(it==M.end())
{
return 1;
fout<<"0\n";
continue;
}
a=it->second;
it=M.upper_bound(c);
--it;
c=it->second;
query(1,n,1);
fout<<sol<<'\n';
}
return 0;
}