Pagini recente » Cod sursa (job #2587300) | Cod sursa (job #1149313) | Cod sursa (job #2988712) | Cod sursa (job #3124241) | Cod sursa (job #739723)
Cod sursa(job #739723)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=16005, RSize=4752001, PSize=600005;
int X[N],Y[N],n, DPrint = -1, DRead;
char PRINT[N], READ[N];
ifstream in("zoo.in");
ofstream out("zoo.out");
vector<int> aib[N];
inline bool cifra(char& c)
{
return '0'<=c && c<='9';
}
void read_int(int& x)
{
while (!cifra(READ[DRead]))
DRead++;
x=0;
while (cifra(READ[DRead]))
x = x * 10 + READ[DRead++] - '0';
}
struct Punct
{
int x,y;
void get()
{
read_int(x);
read_int(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";
}
void add_to_print(int x)
{
if (x<10)
{
PRINT[++DPrint] = x + '0';
PRINT[++DPrint] = '\n';
return;
}
add_to_print(x/10);
PRINT[++DPrint] = x%10 + '0';
}
int main()
{
int m, x, y, z, t;
in.getline(READ,RSize, '\0');
read_int(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);
read_int(m);
while (m--)
{
read_int(x);
read_int(y);
read_int(z);
read_int(t);
x=find(X, x-1);
y=find(Y, y-1);
z=find(X, z);
t=find(Y, t);
add_to_print(query(z,y,t) - query(x,y,t));
}
out<<PRINT;
return 0;
}