Pagini recente » Cod sursa (job #1348874) | Cod sursa (job #1387084) | Cod sursa (job #1847748) | Cod sursa (job #3149481) | Cod sursa (job #739719)
Cod sursa(job #739719)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=16005;
int X[N],Y[N],n;
vector<int> aib[N];
ifstream in("zoo.in");
ofstream out("zoo.out");
struct Punct
{
int x,y;
void get()
{
in >> x >> y;
}
bool operator<(const Punct& P) const
{
return y < P.y;
}
} Points[N];
int find(int v[],int x)
{
int i, step = 1<<13;
for (i = 0 ; step ; step >>= 1)
if (i + step <= v[0] && v[i+step] <= x)
i += step;
return i;
}
int find(vector<int>& v, int x)
{
int i, step = 1<<13;
for (i = -1 ; step ; step >>= 1)
if (i + step < v.size() && v[i+step] <= x)
i += step;
return i;
}
inline int step(int& x)
{
return x & (-x);
}
void update(int x, int val)
{
for ( ; x<=n ; x += step(x))
aib[x].push_back(val);
}
int query(int x, int st, int dr)
{
int rez = 0;
for ( ; x ; x -= step(x))
rez += find(aib[x], dr) - find(aib[x], st);
return rez;
}
void normalise(int v[])
{
v[0] = 1;
for (int i = 2 ; i <= n ; i++)
if (v[i] != v[i-1])
v[++v[0]]=v[i];
}
void print (int v[])
{
for (int i = 1 ; i <= v[0] ; i++)
cout<<v[i]<<" ";
cout<<"\n";
}
void print (vector<int>& v)
{
for (vector<int> :: iterator it = v.begin() ; it != v.end() ; it++)
cout<<(*it)<<" ";
cout<<"\n";
}
int main()
{
int m, x, y, z, t;
in>>n;
for (int i = 1 ; i <= n ; i++)
{
Points[i].get();
X[i]=Points[i].x;
Y[i]=Points[i].y;
}
sort (X + 1, X + n + 1);
sort (Y + 1, Y + n + 1);
normalise(X);
normalise(Y);
for (int i = 1 ; i <= n ; i++)
{
Points[i].x = find(X, Points[i].x);
Points[i].y = find(Y, Points[i].y);
}
sort (Points + 1, Points + n + 1);
for (int i = 1 ; i <= n ; i++)
update(Points[i].x, Points[i].y);
in>>m;
while (m--)
{
in>>x>>y>>z>>t;
x=find(X, x-1);
y=find(Y, y-1);
z=find(X, z);
t=find(Y, t);
out<<query(z,y,t) - query(x,y,t)<<"\n";
}
return 0;
}