Pagini recente » Cod sursa (job #565963) | Cod sursa (job #2668078) | Cod sursa (job #243179) | Cod sursa (job #2543177) | Cod sursa (job #2962861)
#include<fstream>
#include<vector>
#include<algorithm>
#define eb emplace_back
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct punct
{
int x,y;
};
const int NMAX = 16e3 + 1;
vector<vector<int>> aint(4 * NMAX);
vector<punct> puncte;
int qst,qdr,sus,jos;
int get_posst(int x,int n)
{
///caut prima pozitie mai mare sau egala cu x
int st = 0,dr = n - 1,ans = -1;
while(st <= dr)
{
int mid = st + (dr - st) / 2;
if(puncte[mid].x >= x)
ans = mid,dr = mid - 1;
else st = mid + 1;
}
if(ans == -1)
ans = x > puncte[0].x ? n - 1 : 0;
return ans;
}
int get_posdr(int x,int n)
{
///ultima pozitie mai mica sau egala cu x
int st = 0,dr = n - 1,ans = -1;
while(st <= dr)
{
int mid = st + (dr - st) / 2;
if(x >= puncte[mid].x)
ans = mid,st = mid + 1;
else dr = mid - 1;
}
if(ans == -1) exit(69);
return ans;
}
bool cmp(const punct &a,const punct &b)
{
return a.x < b.x;
}
void build(int nod,int st,int dr)
{
if(st == dr)
{
aint[nod].eb(puncte[st].y);
return;
}
int mid = st + (dr - st) / 2;
build(2 * nod,st,mid);
build(2 * nod + 1,mid + 1,dr);
///interclasare
int left = 2 * nod;
int right = left + 1;
int i = 0,j = 0,n = aint[left].size(),m = aint[right].size();
while(i < n && j < m) aint[left][i] < aint[right][j] ? aint[nod].eb(aint[left][i++]): aint[nod].eb(aint[right][j++]);
while(i < n) aint[nod].eb(aint[left][i++]);
while(j < m) aint[nod].eb(aint[right][j++]);
}
int query(int nod,int st,int dr)
{
if(qst <= st && qdr >= dr)
{
int cate = upper_bound(aint[nod].begin(),aint[nod].end(),sus) - aint[nod].begin();
cate -= lower_bound(aint[nod].begin(),aint[nod].end(),jos) - aint[nod].begin();
return cate;
}
int mid = st + (dr - st) / 2;
int ans = 0;
if(qst <= mid) ans += query(2 * nod,st,mid);
if(qdr > mid) ans += query(2 * nod + 1,mid + 1,dr);
return ans;
}
int main()
{
int n,q; fin >> n;
puncte.resize(n);
for(int i = 0; i < n ; i++)
fin >> puncte[i].x >> puncte[i].y;
sort(puncte.begin(),puncte.end(),cmp);
build(1,0,n - 1);
fin >> q;
while(q--)
{
fin >> qst >> jos >> qdr >> sus;
if(qst > puncte[n - 1].x || qdr < puncte[0].x){fout << "0\n";continue;}
qst = get_posst(qst,n),qdr = get_posdr(qdr,n);
fout << query(1,0,n - 1) << '\n' ;
}
}