Pagini recente » Cod sursa (job #1493370) | Cod sursa (job #641990) | Cod sursa (job #2380993) | Cod sursa (job #292947) | Cod sursa (job #833073)
Cod sursa(job #833073)
#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;
vector< pair<int,int> > v;
vector<int> t[50000];
int n,l,r,yl,yr,sum;
void buildTree(int nod, int left, int right){
if(left==right){
t[nod].push_back(0);
t[nod].push_back(v[left].second);
// cout<<nod<<':'<<left<<'-'<<right<<"->";
// cout<<t[nod][0]<<'\n';
return;
}
int mij=(left+right)/2;
buildTree(nod*2,left,mij);
buildTree(nod*2+1,mij+1,right);
t[nod].push_back(0);
t[nod].resize(t[nod*2+1].size()+t[nod*2].size()-1);
merge(t[nod*2].begin()+1,t[nod*2].end(),t[nod*2+1].begin()+1,t[nod*2+1].end(),t[nod].begin()+1);
// vector<int>::iterator it;
// cout<<nod<<':'<<left<<'-'<<right<<"->";
// for(it=t[nod].begin();it!=t[nod].end();++it)
// cout<<*it<<' ';
// cout<<'\n';
}
int qMin(int x){
int left=1,right=n,mij,k=-1;;
while(left<right){
mij=(left+right)/2;
if(x==v[mij].first){
right=mij-1; k=mij;
continue;
}
if(x<v[mij].first)
right=mij-1;
else
left=mij+1;
}
if(k>0) return k;
return left;
}
int qMax(int x){
int left=l,right=n,mij,k=-1;
while(left<right){
mij=(left+right)/2;
if(x==v[mij].first){
left=mij+1; k=mij;
continue;
}
if(x>v[mij].first)
left=mij+1;
else
right=mij-1;
}
if(k>0) return k;
return right;
}
int rez(int x){
int left,right,mij,r,k;
left=1; right=t[x].size()-1; k=-1;
while(left<right){
mij=(left+right)/2;
if(yl==t[x][mij]){
right=mij-1; k=mij;
continue;
}
if(yl<t[x][mij])
right=mij-1;
else
left=mij+1;
}
if(k>0) left=k;
r=left;
right=t[x].size()-1; k=-1;
while(left<right){
mij=(left+right)/2;
if(yr==t[x][mij]){
left=mij+1; k=mij;
continue;
}
if(yr>t[x][mij])
left=mij+1;
else
right=mij-1;
}
if(k>0) return k-r+1;
return right-r+1;
}
void query(int nod, int left, int right){
if(l<=left && right<=r){
sum+=rez(nod);
return;
}
int mij=(left+right)/2;
if(l<=mij) query(nod*2,left,mij);
if(r>mij) query(nod*2+1,mij+1,right);
}
int main(){
ifstream fin("zoo.in");
ofstream fout("zoo.out");
fin>>n;
pair<int,int> x;
int i; v.push_back(x);
for(i=0;i<n;++i){
fin>>x.first>>x.second;
v.push_back(x);
}
sort(v.begin()+1,v.end());
buildTree(1,1,n);
int m;
pair<int,int> a,b;
fin>>m;
for(i=0;i<m;++i){
fin>>a.first>>a.second>>b.first>>b.second;
l=qMin(a.first); yl=a.second;
r=qMax(b.first); yr=b.second;
// cout<<l<<' ';
// cout<<' '<<r<<'\n';
sum=0;
query(1,1,n);
fout<<sum<< '\n';
// cout<<sum<<'\n';
}
// vector< pair<int,int> >::iterator it;
// for(it=v.begin();it!=v.end();++it){
// cout<<it->first<<','<<it->second<<' ';
// }
return 0;
}