Pagini recente » Cod sursa (job #3150220) | Cod sursa (job #1265717) | Cod sursa (job #163528) | Cod sursa (job #1679189) | Cod sursa (job #828261)
Cod sursa(job #828261)
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define left_son ((nod)<<1)
#define right_son ((nod)<<1)+1
#define MAX_SIZE 16000
using namespace std;
typedef struct
{
int x;
int y;
}punct;
vector <int> tree[3*MAX_SIZE];
punct vect[MAX_SIZE+1];
int N;
int y1 , y2;
int answer;
bool cmp(punct a1 , punct a2)
{
return (a1.x < a2.x);
}
int vect_search_right(int value)
{
int left = 1;
int right = N;
int poz = -1;
while (left <= right)
{
int middle = (left + right) >> 1;
if (vect[middle].x <= value)
{
left = middle+1;
poz = middle;
}
else
{
right = middle-1;
}
}
return poz;
}
int vect_search_left(int value)
{
int left = 1;
int right = N;
int poz = -1;
while (left <= right)
{
int middle = (left + right) >> 1;
if (vect[middle].x >= value)
{
right = middle-1;
poz = middle;
}
else
{
right = middle-1;
}
}
return poz;
}
int tree_search_left(int nod , int value)
{
int left = 0;
int right = tree[nod].size()-1;
int poz = -1;
while (left <= right)
{
int middle = (left + right) >> 1;
if (tree[nod][middle] >= value)
{
right = middle-1;
poz = middle;
}
else
{
right = middle-1;
}
}
return poz;
}
int tree_search_right(int nod , int value)
{
int left = 0;
int right = tree[nod].size()-1;
int poz = -1;
while (left <= right)
{
int middle = (left + right) >> 1;
if (tree[nod][middle] <= value)
{
left = middle+1;
poz = middle;
}
else
{
right = middle-1;
}
}
return poz;
}
void build_tree(int nod , int left , int right)
{
if (left == right)
{
tree[nod].push_back(vect[left].y);
return;
}
int middle = (left + right) >> 1;
build_tree(left_son,left,middle);
build_tree(right_son,middle+1,right);
int size1 = tree[left_son].size();
int size2 = tree[right_son].size();
int k1 = 0;
int k2 = 0;
while (k1 < size1 && k2 < size2)
{
if (tree[left_son][k1] < tree[right_son][k2])
{
tree[nod].push_back(tree[left_son][k1]);
k1++;
}
else
{
tree[nod].push_back(tree[right_son][k2]);
k2++;
}
}
while (k1 < size1)
{
tree[nod].push_back(tree[left_son][k1]);
k1++;
}
while (k2 < size2)
{
tree[nod].push_back(tree[right_son][k2]);
k2++;
}
}
void query_tree(int nod , int left , int right , int A , int B)
{
if ( A <= left && right <= B)
{
int poz1 = tree_search_left(nod,y1);
int poz2 = tree_search_right(nod,y2);
if (poz1 != -1 && poz2 != -1)
answer += poz2 - poz1 + 1;
return;
}
int middle = (left + right) >> 1;
if (middle >= A) query_tree(left_son,left,middle,A,B);
if (B> middle) query_tree(right_son,middle+1,right,A,B);
}
int main()
{
ifstream input("zoo.in");
ofstream output("zoo.out");
input >> N;
for (int i = 1;i<=N;i++)
{
input >> vect[i].x >> vect[i].y;
}
sort(vect+1 , vect + N + 1 , cmp);
build_tree(1,1,N);
int M;
input >> M;
for (int i = 0 ; i < M;i++)
{
punct a1;
punct a2;
input >> a1.x >> a1.y >> a2.x >> a2.y;
int poz1 = vect_search_left(a1.x);
int poz2 = vect_search_right(a2.x);
y1 = a1.y;
y2 = a2.y;
answer = 0;
if (poz1 != -1 && poz2 != -1)
{
query_tree(1,1,N,poz1,poz2);
output << answer << "\n";
}
else
{
output << 0;
}
}
input.close();
output.close();
return 0;
}