Pagini recente » Cod sursa (job #502222) | Cod sursa (job #799463) | Cod sursa (job #269505) | Cod sursa (job #3184721) | Cod sursa (job #2909740)
#include <fstream>
#include <map>
#include <algorithm>
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
int n,i,cnt,m,ok,vv;
map<int,int> ma,ar[100005];
pair<int,int> p[100005],val[200005];
pair<pair<int,int>,pair<int,int> > s[100005];
void upd1(int x,int y,int val)
{
for (int i=x;i<=cnt;i+=(i&(-i)))
for (int j=y;j<=cnt;j+=(j&(-j)))
ar[i][j]+=val;
}
int que(int x,int y)
{
int sum=0;
for (int i=x;i>0;i-=(i&(-i)))
for (int j=y;j>0;j-=(j&(-j)))
sum+=ar[i][j];
return sum;
}
int main()
{
in>>n;
for (i=1;i<=n;++i)
{
in>>p[i].first>>p[i].second;
val[++val[0].first].first=p[i].first;
val[val[0].first].second=1;
val[++val[0].first].first=p[i].second;
val[val[0].first].second=1;
}
in>>m;
for (i=1;i<=m;++i)
{
in>>s[i].first.first>>s[i].first.second>>s[i].second.first>>s[i].second.second;
val[++val[0].first].first=s[i].first.first;
val[++val[0].first].first=s[i].second.first;
val[++val[0].first].first=s[i].first.second;
val[++val[0].first].first=s[i].second.second;
}
sort(val+1,val+val[0].first+1);
cnt=1;
for (i=1;i<=val[0].first;)
{
ok=0;
cnt++;
while (ok==0&&i<=val[0].first){
vv=val[i].first;
ma[vv]=cnt;
while (vv==val[i].first) {ok=((ok)|(val[i].second)); i++;}
}
}
for (i=1;i<=n;++i)
{
p[i].first=ma[p[i].first];
p[i].second=ma[p[i].second];
}
for (i=1;i<=m;++i)
{
s[i].first.first=ma[s[i].first.first];
s[i].first.second=ma[s[i].first.second];
s[i].second.first=ma[s[i].second.first];
s[i].second.second=ma[s[i].second.second];
}
for (i=1;i<=n;++i)
{
upd1(p[i].first,p[i].second,1);
}
for (i=1;i<=m;++i)
{
out<<que(s[i].second.first,s[i].second.second)+que(s[i].first.first-1,s[i].first.second-1)-que(s[i].second.first,s[i].first.second-1)-que(s[i].first.first-1,s[i].second.second);
out<<'\n';
}
return 0;
}