Pagini recente » Cod sursa (job #1833177) | Cod sursa (job #2431494) | Cod sursa (job #811411) | Cod sursa (job #2977723) | Cod sursa (job #3165962)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
#include <set>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
using ll=long long;
const int Nmax=16005,Mmax=100005;
ll sol[Mmax];
pair<ll,ll> q[Mmax];
pair<ll,ll> a[Nmax];
ll b[Nmax];
multiset<ll> s;
vector<pair<int,bool>> ev[Nmax];
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>a[i].first>>a[i].second;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
b[i]=a[i].second;
}
int m;
ll x1,x2,y1,y2;
fin>>m;
for(int i=1;i<=m;i++)
{
fin>>x1>>y1>>x2>>y2;
pair<ll,ll> lb={x1,LLONG_MIN};
int poz1=lower_bound(a+1,a+n+1,lb)-a;
lb={x2,LLONG_MAX};
int poz2=upper_bound(a+1,a+n+1,lb)-a-1;
if(poz2<poz1) sol[i]=0;
else
{
q[i]={y1,y2};
ev[poz1-1].push_back({i,0});
ev[poz2].push_back({i,1});
}
}
for(int i=1;i<=n;i++)
{
s.insert(b[i]);
for(int j=0;j<ev[i].size();j++)
{
int k=ev[i][j].first;
bool tip=ev[i][j].second;
auto it1=lower_bound(s.begin(),s.end(),q[k].first);
auto it2=upper_bound(s.begin(),s.end(),q[k].second);
int d=distance(it1,it2);
if(tip==0) sol[k]-=d;
else sol[k]+=d;
}
}
for(int i=1;i<=m;i++)
{
fout<<sol[i]<<'\n';
}
return 0;
}