Pagini recente » Cod sursa (job #585092) | Cod sursa (job #72489) | Cod sursa (job #969848) | Cod sursa (job #1737145) | Cod sursa (job #2022260)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream si("zoo.in");
ofstream so("zoo.out");
pair<int,int> v[16001];
vector<int>a[16*16001],x;
int lf,rt;
void upd(int nod,int st,int dr)
{
if(st==dr)
{
a[nod].push_back(v[st].second);
return;
}
int mij=(st+dr)>>1;
upd(2*nod,st,mij);
upd(2*nod+1,mij+1,dr);
a[nod].resize(a[2*nod].size()+a[2*nod+1].size());
merge(a[2*nod].begin(),a[2*nod].end(),a[2*nod+1].begin(),a[2*nod+1].end(),a[nod].begin());
}
int rez,l,r,y,b;
void querry(int nod,int st,int dr)
{
if(lf<=st&&dr<=rt)
{
l=lower_bound(a[nod].begin(),a[nod].end(),y)-a[nod].begin();
r=upper_bound(a[nod].begin(),a[nod].end(),b)-a[nod].begin();
rez=rez-l+r;
return;
}
if(st==dr) return;
int mij=(st+dr)>>1;
if (lf<=mij) querry(2*nod,st,mij);
if (mij<rt) querry(2*nod+1,mij+1,dr);
}
int main()
{
int n;
si>>n;
for(int i=1;i<=n;i++)
{
si>>v[i].first>>v[i].second;
x.push_back(v[i].first);
}
sort(x.begin(),x.end());
sort(v+1,v+n+1);
int m;
si>>m;
upd(1,1,n);
for(int i=1;i<=m;i++)
{
int t1,t2;
si>>t1>>y>>t2>>b;
rez=0;
lf=lower_bound(x.begin(),x.end(),t1)-x.begin()+1;
rt=upper_bound(x.begin(),x.end(),t2)-x.begin();
querry(1,1,n);
so<<rez<<'\n';
}
return 0;
}