Pagini recente » Cod sursa (job #675694) | Cod sursa (job #286127) | Cod sursa (job #1983227) | Cod sursa (job #167479) | Cod sursa (job #2908712)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int N = 16000, M = 1e5, MAXY = 3e5;
struct punct{
int x, y;
}v[N + 1];
struct dreptunghi{
int x1, y1, x2, y2;
}d[M + 1];
struct query{
int l, r, val, ind;
}q[2 * M + 1];
bool cmp1(punct a, punct b){
return a.x < b.x;
}
/* ----------------------- AIB ------------------------ */
int aib[MAXY + 1];
int lsb(int x){
return x & -x;
}
void update(int poz, int val){
for(int i = poz; i <= MAXY; i += lsb(i))
aib[i] += val;
}
int query(int poz){
int ans = 0;
for(int i = poz; i >= 1; i -= lsb(i))
ans += aib[i];
return ans;
}
/* ---------------------------------------------------- */
struct upd{
int val, ind, start;
};
/*
start - 0 - incepe jos
- 1 - se termina jos
- 2 - incepe sus
- 3 - se termina sus
*/
vector <upd> lin[MAXY + 1];
struct for_ans{
int sus, jos;
}ans[M + 1];
int main(){
/* ---------------------- citire ---------------------- */
int n;
fin >> n;
for(int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
int m;
fin >> m;
for(int i = 1; i <= m; i++)
fin >> d[i].x1 >> d[i].y1 >> d[i].x2 >> d[i].y2;
/* ---------------------------------------------------- */
/* --------------- normalizare Y ---------------------- */
vector <int> aux;
for(int i = 1; i <= n; i++)
aux.push_back(v[i].y);
for(int i = 1; i <= m; i++)
aux.push_back(d[i].y1), aux.push_back(d[i].y2);
sort(aux.begin(), aux.end());
int ct = 1;
map <int, int> mp;
for(int i = 0; i < (int)aux.size(); i++)
if(mp.find(aux[i]) == mp.end())
mp[aux[i]] = ct++;
for(int i = 1; i <= n; i++)
v[i].y = mp[v[i].y];
for(int i = 1; i <= m; i++)
d[i].y1 = mp[d[i].y1], d[i].y2 = mp[d[i].y2];
/* ---------------------------------------------------- */
/* -------------- stabilim queries -------------------- */
sort(v + 1, v + n + 1, cmp1);
for(int i = 1; i <= m; i++){
int st, dr, ans;
st = 1, dr = n, ans = 0;
while(st <= dr){
int mij = (st + dr) / 2;
if(d[i].x1 < v[mij].x)
st = mij + 1, ans = mij;
else
dr = mij - 1;
}
q[2 * i - 1].l = ans;
q[2 * i].l = ans;
st = 1, dr = n, ans = 0;
while(st <= dr){
int mij = (st + dr) / 2;
if(d[i].x2 <= v[mij].x)
st = mij + 1, ans = mij;
else
dr = mij - 1;
}
q[2 * i - 1].r = ans;
q[2 * i].r = ans;
q[2 * i - 1].val = d[i].y1;
q[2 * i].val = d[i].y2;
q[2 * i - 1].ind = i;
q[2 * i].ind = i;
lin[q[2 * i - 1].l].push_back({q[2 * i - 1].val, q[2 * i - 1].ind, 0});
lin[q[2 * i - 1].r].push_back({q[2 * i - 1].val, q[2 * i - 1].ind, 1});
lin[q[2 * i].l].push_back({q[2 * i].val, q[2 * i].ind, 2});
lin[q[2 * i].r].push_back({q[2 * i].val, q[2 * i].ind, 3});
}
/* ---------------------------------------------------- */
/* ------------------- parcurgere y ------------------- */
for(int i = 1; i <= MAXY; i++){
for(int j = 0; j < (int)lin[i].size(); j++){
if(lin[i][j].start == 0){
ans[lin[i][j].ind].jos -= query(lin[i][j].val - 1);
update(lin[i][j].val, 1);
}else if(lin[i][j].start == 1){
ans[lin[i][j].ind].jos += query(lin[i][j].val - 1);
update(lin[i][j].val, 1);
}else if(lin[i][j].start == 2){
ans[lin[i][j].ind].sus -= query(lin[i][j].val - 1);
update(lin[i][j].val, 1);
}else{
ans[lin[i][j].ind].sus += query(lin[i][j].val - 1);
update(lin[i][j].val, 1);
}
}
}
/* ---------------------------------------------------- */
/* ------------------------ ans ----------------------- */
for(int i = 1; i <= m; i++)
fout << ans[i].sus - ans[i].jos << '\n';
/* ---------------------------------------------------- */
return 0;
}