Pagini recente » Cod sursa (job #1020053) | Cod sursa (job #2878549) | Cod sursa (job #2412911) | Cod sursa (job #2214624) | Cod sursa (job #1134794)
#include <fstream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 16005;
struct Punct{
int x, y;
};
class Aib{
struct Node{
unsigned short int *val;
Node(){
val = NULL;
}
void alloc(int n){
val = (unsigned short int*)malloc( (n + 1) * sizeof(unsigned short int) );
val[0] = 0;
}
inline int size(){
return val[0];
}
inline bool isEmpty(){
return val == NULL;
}
void insert(int x){
val[ ++val[0] ] = x;
}
void prepare(){
sort(val + 1, val + val[0] + 1);
}
int find(int x){
int ans = 0;
for (int step = 1 << ( 31 - __builtin_clz( size() ) ) ; step ; step >>= 1)
if ( (ans ^ step) <= size() && val[ans ^ step] <= x )
ans ^= step;
return ans;
}
};
Node aib[N];
int size;
inline int step(int x){
return x & -x;
}
public:
void init(int n, int* cnt){
size = n;
for (int i = 1 ; i <= n ; i++){
if (i + step(i) <= n)
cnt[ i + step(i) ] += cnt[i];
aib[i].alloc( cnt[i] );
}
}
void insert(int x, int y){
for (int i = x ; i <= size ; i += step(i))
aib[i].insert(y);
}
void pregen(){
for (int i = 1 ; i <= size ; i++)
aib[i].prepare();
}
int query(int x, int y){
if (x <= 0 || y <= 0)
return 0;
int ans = 0;
for (int i = x ; i ; i -= step(i))
ans += aib[i].find(y);
return ans;
}
int query(int x, int y, int z, int t){
return query(z, t) - query(z, y) - query(x, t) + query(x, y);
}
};
int X[N], Y[N], cnt[N], n;
Punct P[N];
Aib A;
void cleanup(int v[], int n){
v[0] = 1;
sort(v + 1, v + n + 1);
for (int i = 2 ; i <= n ; i++)
if ( v[i] != v[i - 1] )
v[ ++v[0] ] = v[i];
}
int norm(int v[], int x){
int ans = 0;
for (int step = 1 << (31 - __builtin_clz( v[0] ) ) ; step ; step >>= 1)
if ( (ans ^ step) <= v[0] && v[ans ^ step] <= x )
ans ^= step;
return ans;
}
int main(){
int x, y, z, t, nrQ;
ifstream in("zoo.in");
ofstream out("zoo.out");
in >> n;
for (int i = 1 ; i <= n ; i++){
in >> P[i].x >> P[i].y;
X[i] = P[i].x;
Y[i] = P[i].y;
}
cleanup(X, n);
cleanup(Y, n);
for (int i = 1 ; i <= n ; i++)
cnt[ norm(X, P[i].x) ]++;
A.init(X[0], cnt);
for (int i = 1 ; i <= n ; i++)
A.insert( norm(X, P[i].x), norm(Y, P[i].y) );
A.pregen();
in >> nrQ;
while (nrQ--){
in >> x >> y >> z >> t; x--; y--;
out << A.query( norm(X, x), norm(Y, y), norm(X, z), norm(Y, t) ) << "\n";
}
return 0;
}