Pagini recente » Cod sursa (job #739828) | Cod sursa (job #2716879) | Cod sursa (job #2008329) | Cod sursa (job #3003145) | Cod sursa (job #828359)
Cod sursa(job #828359)
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define MAX_SIZE 16000
#include <string.h>
using namespace std;
typedef struct
{
int x;
int y;
}punct;
vector <int> tree[1 << 15];
punct vect[MAX_SIZE+1];
int N;
int y1 , y2;
char buffer[56];
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
{
left = middle+1;
}
}
return poz;
}
int tree_search_left(int nod , int value)
{
int size = tree[nod].size();
if(tree[nod][size-1] < value)
{
return -1;
}
return (lower_bound(tree[nod].begin(), tree[nod].end(),value) - tree[nod].begin());
}
int tree_search_right(int nod , int value)
{
int size = tree[nod].size();
if(tree[nod][0] > value)
{
return -1;
}
return (lower_bound(tree[nod].begin(),tree[nod].end(),value+1) - tree[nod].begin() - 1);
}
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(2*nod,left,middle);
build_tree(2*nod+1,middle+1,right);
int size1 = tree[2*nod].size();
int size2 = tree[2*nod+1].size();
int k1 = 0;
int k2 = 0;
while (k1 < size1 && k2 < size2)
{
if (tree[2*nod][k1] < tree[2*nod+1][k2])
{
tree[nod].push_back(tree[2*nod][k1]);
k1++;
}
else
{
tree[nod].push_back(tree[2*nod+1][k2]);
k2++;
}
}
while (k1 < size1)
{
tree[nod].push_back(tree[2*nod][k1]);
k1++;
}
while (k2 < size2)
{
tree[nod].push_back(tree[2*nod+1][k2]);
k2++;
}
}
int 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)
return poz2 - poz1 + 1;
else return 0;
}
int middle = (left + right) >> 1;
int r1= 0,r2 = 0;
if (middle >= A) r1 = query_tree(2*nod,left,middle,A,B);
if (B> middle) r2 = query_tree(2*nod+1,middle+1,right,A,B);
return r1+r2;
}
int convert_to_number(int &poz)
{
int semn = 1;
if (buffer[poz] == '-')
{
semn *= -1;
poz++;
}
int number = 0;
while ( poz < strlen(buffer) && buffer[poz] != ' ')
{
number = number * 10 + (buffer[poz] - '0');
poz++;
}
poz++;
return semn * number;
}
int main()
{
ifstream input("zoo.in");
ofstream output("zoo.out");
int pos = 0;
input.getline(buffer,56);
N = convert_to_number(pos);
for (int i = 1;i<=N;i++)
{
pos = 0;
input.getline(buffer,56);
vect[i].x = convert_to_number(pos);
vect[i].y = convert_to_number(pos);
}
sort(vect+1 , vect + N + 1 , cmp);
build_tree(1,1,N);
pos = 0;
input.getline(buffer,56);
int M = convert_to_number(pos);
for (int i = 0 ; i < M;i++)
{
pos = 0;
input.getline(buffer,56);
int x1 = convert_to_number(pos);
y1 = convert_to_number(pos);
int x2 = convert_to_number(pos);
y2 = convert_to_number(pos);
int poz1 = vect_search_left(x1);
int poz2 = vect_search_right(x2);
int answer = 0;
if (poz1 != -1 && poz2 != -1)
{
answer = query_tree(1,1,N,poz1,poz2);
}
output << answer << "\n";
}
input.close();
output.close();
return 0;
}