Pagini recente » Cod sursa (job #1292566) | Cod sursa (job #1185784) | Cod sursa (job #1920121) | Cod sursa (job #1593048) | Cod sursa (job #1490367)
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
class orthogonal_range_search{
const int n;
vector<vector<int> > points;
vector<int> xs;
public:
explicit orthogonal_range_search(vector<pair<int, int> >& pts):
n(pts.size()), points(2*n){
sort(begin(pts), end(pts), [](const pair<int, int> a, const pair<int, int> b){
return a.first < b.first; });
for(int i = 0; i < pts.size(); ++i){
xs.push_back(pts[i].first);
points[i+n].push_back(pts[i].second); }
for(int i = n-1; i > 0; --i){
points[i].resize(points[2*i].size() +
points[2*i+1].size());
merge(begin(points[2*i]), end(points[2*i]),
begin(points[2*i+1]), end(points[2*i+1]),
begin(points[i])); } }
int query(const int x1, const int y1, const int x2, const int y2){
int rez = 0;
for(int st = lower_bound(begin(xs), end(xs), x1)-begin(xs)+n,
dr = upper_bound(begin(xs), end(xs), x2)-begin(xs)+n;
st < dr;
st /= 2, dr /= 2){
if(st%2 == 1){
rez += upper_bound(begin(points[st]), end(points[st]), y2) -
lower_bound(begin(points[st]), end(points[st]), y1);
++st; }
if(dr%2 == 1){
--dr;
rez += upper_bound(begin(points[dr]), end(points[dr]), y2) -
lower_bound(begin(points[dr]), end(points[dr]), y1); } }
return rez; } };
int main(){
ifstream f("zoo.in");
ofstream g("zoo.out");
int n;
f >> n;
vector<pair<int, int> > v(n);
for(auto& x : v){
f >> x.first >> x.second; }
orthogonal_range_search ors(v);
int m;
f >> m;
for(int i = 0, x1, y1, x2, y2; i < m; ++i){
f >> x1 >> y1 >> x2 >> y2;
g << ors.query(x1, y1, x2, y2) << '\n'; }
return 0; }