Pagini recente » Cod sursa (job #1077877) | Cod sursa (job #116360) | Cod sursa (job #2140379) | Cod sursa (job #2061010) | Cod sursa (job #3163516)
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <cmath>
#include <vector>
#define DIM 16000
using namespace std;
//ifstream f("in.in");
//ofstream g("out.out");
ifstream f("zoo.in");
ofstream g("zoo.out");
struct info{
int x,y;
};
bool cmp(info a,info b){
return a.x<b.x;
}
info v[DIM+5];
int n,m,X1,X2,Y1,Y2;
vector<int> a[4*DIM+5];
void build(int nod,int st,int dr){
if(st == dr){
a[nod].push_back(v[dr].y);
//cout<<st<<"-"<<dr<<": "<<v[dr].y<<"\n";
return;
}
int mid = (st+dr)/2;
build(2*nod,st,mid);
build(2*nod+1,mid+1,dr);
int i=0,j=0,x,y;
x = a[2*nod].size();
y = a[2*nod+1].size();
while(i<x && j<y){
if(a[2*nod][i]<a[2*nod+1][j]){
a[nod].push_back(a[2*nod][i]);
i++;
}else{
a[nod].push_back(a[2*nod+1][j]);
j++;
}
}
while(i<x){
a[nod].push_back(a[2*nod][i]);
i++;
}
while(j<y){
a[nod].push_back(a[2*nod+1][j]);
j++;
}
/*cout<<st<<"-"<<dr<<": ";
for(int i=0;i<a[nod].size();i++){
cout<<a[nod][i]<<" ";
}cout<<"\n";*/
}
int findFirst(int nod,int x){
int st=0,dr=a[nod].size()-1;
while(st<=dr){
int mid = (st+dr)/2;
if(x<=a[nod][mid]){
dr = mid-1;
}else{
st = mid+1;
}
}
return st;
}
int findLast(int nod,int x){
int st=0,dr=a[nod].size()-1;
while(st<=dr){
int mid = (st+dr)/2;
if(a[nod][mid]<=x){
st = mid+1;
}else{
dr = mid-1;
}
}
return dr;
}
int sol = 0;
void query(int nod,int st,int dr){
if(X1<=v[st].x && v[dr].x<=X2){
sol += (findLast(nod,Y2) - findFirst(nod,Y1)+1);
return;
}
if(st == dr){
return;
}
int mid = (st+dr)/2;
if(X1<=v[mid].x){
query(2*nod,st,mid);
}
if(v[mid+1].x <= X2){
query(2*nod+1,mid+1,dr);
}
}
int main()
{
f>>n;
for(int i=1;i<=n;i++){
f>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
build(1,1,n);
f>>m;
for(int i=1;i<=m;i++){
f>>X1>>Y1>>X2>>Y2;
sol=0;
query(1,1,n);
g<<sol<<'\n';
}
return 0;
}