Pagini recente » Cod sursa (job #149819) | Cod sursa (job #1986321) | Cod sursa (job #2495703) | Cod sursa (job #1880153) | Cod sursa (job #1546844)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 16000
#define x first
#define y second
#define PUT 14
using namespace std;
typedef pair <int, int> punct;
typedef vector <punct> lst;
lst Aint[(5 * MAXN) + 1];
lst v;
int n, m;
void buildT(int node, int l, int r) {
if (l == r)
Aint[node].push_back(v[l]);
else {
int mid = (l + r) >> 1;
int left_son = node * 2, right_son = (node * 2) + 1;
buildT(left_son, l, mid);
buildT(right_son, mid + 1, r);
//Aint[node] = interclasare
int p1 = 0, p2 = 0;
while (p1 < Aint[left_son].size() && p2 < Aint[right_son].size()) {
int pl1 = 0, pl2 = 1;
punct P = Aint[right_son][p2];
if (Aint[left_son][p1].y < Aint[right_son][p2].y) {
P = Aint[left_son][p1];
pl1 = 1;
pl2 = 0;
}
Aint[node].push_back(P);
p1 += pl1;
p2 += pl2;
}
while (p1 < Aint[left_son].size())
Aint[node].push_back(Aint[left_son][p1++]);
while (p2 < Aint[right_son].size())
Aint[node].push_back(Aint[right_son][p2++]);
}
}
inline int binsearch1(int node, int val) {
int sol = 0, pas = (1 << 14);
while (pas) {
int pos = sol + pas;
//if (pos <Aint[node].size())
//cerr<<Aint[node][pos].x<<" "<<Aint[node][pos].y<<"\n";
if (pos < Aint[node].size() && Aint[node][pos].y < val)
sol = pos;
pas >>= 1;
}
if (Aint[node][sol].y < val)
++sol;
if (sol >= Aint[node].size())
return -1;
if (Aint[node][sol].y < val)
return -1;
return sol;
}
inline int binsearch2(int node, int val) {
int sol = 0, pas = (1 << 14);
while (pas) {
int pos = sol + pas;
if (pos < Aint[node].size() && Aint[node][pos].y <= val)
sol = pos;
pas >>= 1;
}
if (Aint[node][sol].y <= val)
++sol;
if (sol >= Aint[node].size())
return -1;
if (Aint[node][sol].y <= val)
return -1;
return sol;
}
inline int cauta(int node, punct P1, punct P2) {
int pos1 = binsearch1(node, P1.y), pos2 = binsearch2(node, P2.y); //prima pos >= si prima pos mai mare.
if (pos1 == -1)
return 0;
if (pos2 == 0)
return 0;
if (pos2 == -1) {
pos2 = Aint[node].size() - 1;
}
else
--pos2;
return pos2 - pos1 + 1;
}
int Query(int node, int l, int r, punct P1, punct P2) {
if (v[r].x < P1.x || v[l].x > P2.x)
return 0;
if (v[l].x >= P1.x && v[r].x <= P2.y)
return cauta(node, P1, P2);
int mid = (l + r) >> 1;
int left_son = node * 2, right_son = (node * 2) + 1;
return Query(left_son, l, mid, P1, P2) + Query(right_son, mid + 1, r, P1, P2);
}
int main () {
ifstream cin("zoo.in");
ofstream cout("zoo.out");
cin >> n;
for (int i = 0 ; i < n ; ++i) {
punct pc;
cin >> pc.x >> pc.y;
v.push_back(pc);
}
sort(v.begin(), v.end());
buildT(1, 0, n - 1);
cin >> m;
for (int i = 0 ; i < m ; ++i) {
punct P1, P2;
cin >> P1.x >> P1.y >> P2.x >> P2.y;
cout << Query(1, 0, n - 1, P1, P2) << "\n";
}
return 0;
}