Pagini recente » Borderou de evaluare (job #698909) | Borderou de evaluare (job #2367724) | Cod sursa (job #2341705) | Cod sursa (job #1988651) | Cod sursa (job #3161910)
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define DIMN 16010
#define DIMM 100010
using namespace std;
struct drept{
int x1;
int y1;
int x2;
int y2;
};
vector<int> all;
set<int> s;
pair<int, int> p[DIMN];
drept d[DIMM];
int n, m, i, sol;
vector<pair<int, int>> A[4*DIMN];
void build(int nod, int st, int dr) {
for (int i=st;i<=dr;i++) {
A[nod].push_back({p[i].second, p[i].first});
sort(A[nod].begin(), A[nod].end());
}
if (st < dr) {
int mid = (st+dr)/2;
build(2*nod, st, mid);
build(2*nod+1, mid+1, dr);
}
}
int cauta_primul (int x, int nod) {
int st = 0;
int dr = A[nod].size()-1;
while (st <= dr) {
int mid = (st+dr)/2;
if (x <= A[nod][mid].first)
dr = mid-1;
else
st = mid+1;
}
return st;
}
int cauta_ultimul (int x, int nod) {
int st = 0;
int dr = A[nod].size()-1;
while (st <= dr) {
int mid = (st+dr)/2;
if (x >= A[nod][mid].first)
st = mid+1;
else
dr = mid-1;
}
return dr;
}
void query(int nod, int st, int dr, int poz) {
if(d[poz].x1 <= p[st].first && d[poz].x2 >=p[dr].first) {
/// in vectorul A[nod] avem elementele sortate dupa first (care este de fapt y)
/// ne intereseaza cate elemente au aceasta valoare cuprinsa intre
/// d[poz].y1 si d[poz].y2
/// astfel, cautam prima valoare mai mare sau egala cu d[poz].y1 si ultima
/// mai mica sau egala cu d[poz].y2.
sol += (cauta_ultimul(d[poz].y2, nod) - cauta_primul(d[poz].y1, nod) + 1);
} else {
int mid = (st + dr) / 2;
if (d[poz].x1 <= p[mid].first)
query(2*nod, st, mid, poz);
if (d[poz].x2 >= p[mid+1].first)
query(2*nod+1, mid+1, dr, poz);
}
}
int main () {
ifstream fin ("zoo.in");
ofstream fout("zoo.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>p[i].first>>p[i].second;
s.insert(p[i].first);
s.insert(p[i].second);
}
fin>>m;
for (i=1;i<=m;i++) {
fin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
s.insert(d[i].x1);
s.insert(d[i].y1);
s.insert(d[i].x2);
s.insert(d[i].y2);
}
for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
all.push_back(*it);
}
for (i=1;i<=n;i++) {
p[i].first = lower_bound (all.begin(), all.end(), p[i].first) - all.begin();
p[i].second = lower_bound (all.begin(), all.end(), p[i].second) - all.begin();
}
for (i=1;i<=m;i++) {
d[i].x1 = lower_bound (all.begin(), all.end(), d[i].x1) - all.begin();
d[i].y1 = lower_bound (all.begin(), all.end(), d[i].y1) - all.begin();
d[i].x2 = lower_bound (all.begin(), all.end(), d[i].x2) - all.begin();
d[i].y2 = lower_bound (all.begin(), all.end(), d[i].y2) - all.begin();
}
/**
for (i=1;i<=n;i++) {
cout<<p[i].first<<" "<<p[i].second<<"\n";
}
for (i=1;i<=m;i++) {
cout<<d[i].x1<<" "<<d[i].y1<<" "<<d[i].x2<<" "<<d[i].y2<<"\n";
}
**/
sort(p+1, p+n+1);
build(1, 1, n);
for (int i=1;i<=m;i++) {
sol = 0;
query(1, 1, n, i);
fout<<sol<<"\n";
}
return 0;
}