Pagini recente » Cod sursa (job #1890596) | Cod sursa (job #1996377) | Cod sursa (job #1590094) | Cod sursa (job #2807161) | Cod sursa (job #1233927)
#include <fstream>
//#include <iostream>
#include <algorithm>
#include <vector>
//#include <map>
#include <set>
#include <cstring>
#include <cctype>
#include <cassert>
#define NMAX 36005
#define MMAX 100005
#define lsb(x) ((x)&(-x))
using namespace std;
int aib[16005];
int marime;
inline void update(int i){
for(;i<=marime;i+=lsb(i))
aib[i]++;
}
inline int query(int i){
int s=0;
for(;i;i-=lsb(i))
s+=aib[i];
return s;
}
int ans[MMAX];
//Parsare
//ifstream cin("zoo.in");
/*
char sir[6496005];
int lung,poz;
inline void cit(){
cin.get(sir+1,6496005,'#');
lung=strlen(sir+1);
poz=1;
}
inline int extract(){
while(poz<=lung && (!isdigit(sir[poz]) && sir[poz]!='-'))
++poz;
int semn=1;
if(sir[poz]=='-'){
semn=-1;
++poz;
}
int rez=0;
while(poz<=lung && isdigit(sir[poz])){
rez*=10;
rez+=(sir[poz]-'0');
++poz;
}
return (semn*rez);
}*/
//End of Parsare
struct operatie
{
int x,y;
int tip;
int poz;
}op[NMAX+4*MMAX];
bool operator<(const operatie &a,const operatie &b){
if(a.x<b.x)
return 1;
if(a.x>b.x)
return 0;
return a.tip<b.tip;
}
int main()
{
ios_base::sync_with_stdio(false);
ifstream cin("zoo.in");
ofstream cout("zoo.out");
//set<int> setx,sety;
vector<int> setx,sety;
//map<int,int> hartax;
//map<int,int> hartay;
int n=0;
//cit();
cin>>n;
//n=extract();
set<int> verifx;
set<int> verify;
//Normalizare
setx.push_back(-2000000005);
setx.push_back(2000000005);
sety.push_back(-2000000005);
sety.push_back(2000000005);
for(int i=1;i<=n;++i){
//cin>>x>>y;
cin>>op[i].x;//=extract();
cin>>op[i].y;//=extract();
op[i].poz=i;
//setx.insert(v[i].x);
//sety.insert(v[i].y);
if(!verifx.count(op[i].x)){
setx.push_back(op[i].x);
verifx.insert(op[i].x);
}
if(!verify.count(op[i].y)){
sety.push_back(op[i].y);
verify.insert(op[i].y);
}
}
sort(setx.begin(),setx.end());
sort(sety.begin(),sety.end());
/*vector<int>::iterator it;
int i=1;
hartax[setx[0]]=1;
for(int j=1;j<setx.size();++j)
if(setx[j-1]!=setx[j])
hartax[setx[j]]=++i;
i=1;
hartay[sety[0]]=1;
for(int j=1;j<sety.size();++j)
if(sety[j-1]!=sety[j])
hartay[sety[j]]=++i;
*/
for(int i=1;i<=n;++i){
//op[i].x=hartax[op[i].x];
//op[i].y=hartay[op[i].y];
op[i].x=lower_bound(setx.begin(),setx.end(),op[i].x)-setx.begin()+1;
op[i].y=lower_bound(sety.begin(),sety.end(),op[i].y)-sety.begin()+1;
}
//End of Normalizare
int m=0;
cin>>m;
//m=extract();
int x1,y1,x2,y2;
//map<int,int>::iterator itt;
int poz=n;
for(int i=1;i<=m;++i){
cin>>x1>>y1>>x2>>y2;
//x1=extract();
//y1=extract();
//x2=extract();
//y2=extract();
//itt=hartay.lower_bound(y1);itt--;
//y1=itt->second;
y1=lower_bound(sety.begin(),sety.end(),y1)-sety.begin();
//itt=hartay.upper_bound(y2);itt--;
//y2=itt->second;
y2=upper_bound(sety.begin(),sety.end(),y2)-sety.begin();
//itt=hartax.lower_bound(x1);itt--;
//x1=itt->second;
x1=lower_bound(setx.begin(),setx.end(),x1)-setx.begin();
//itt=hartax.upper_bound(x2);itt--;
//x2=itt->second;
x2=upper_bound(setx.begin(),setx.end(),x2)-setx.begin();
assert(y1 && y1 && x1 && x2);
//cout<<"am citit "<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
if(y1<=y2 && x1<=x2){
//cout<<query(y1,y2,1,x2-1)-query(y1,y2,1,x1-1)<<'\n';
op[++poz].poz=i;
op[poz].tip=1;
op[poz].x=x2;
op[poz].y=y2;
op[++poz].poz=i;
op[poz].tip=1;
op[poz].x=x1;
op[poz].y=y1;
op[++poz].poz=i;
op[poz].tip=2;
op[poz].x=x1;
op[poz].y=y2;
op[++poz].poz=i;
op[poz].tip=2;
op[poz].x=x2;
op[poz].y=y1;
}
}
sort(op+1,op+poz+1);
marime=setx.size()+1;
for(int i=1;i<=poz;++i)
if(!op[i].tip)
update(op[i].y);
else if(op[i].tip==1)
ans[op[i].poz]+=query(op[i].y);
else
ans[op[i].poz]-=query(op[i].y);
for(int i=1;i<=m;++i){
cout<<ans[i]<<'\n';
assert(ans[i]>=0);
}
cin.close();
cout.close();
return 0;
}