Pagini recente » Cod sursa (job #2655872) | Cod sursa (job #622759) | Cod sursa (job #3203804) | Cod sursa (job #55376) | Cod sursa (job #1134133)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 16001;
struct Punct{
int x, y;
inline bool operator<(const Punct& P) const {
return x < P.x || (x == P.x && y < P.y);
}
};
class Aib{
vector<int> aib[N];
int size;
inline int step(int x){
return x & -x;
}
int find(vector<int>& v, int x){
if (v.empty() || x < v[0])
return 0;
int ans = 0;
for (int step = 1 << 13 ; step ; step >>= 1)
if ( (ans ^ step) < v.size() && v[ans ^ step] <= x )
ans ^= step;
return ans + 1;
}
public:
void init(int n){
size = n;
}
void insert(int x, int y){
for (int i = x ; i <= size ; i += step(i))
aib[i].push_back(y);
}
int query(int x, int y){
int ans = 0;
for (int i = x ; i ; i -= step(i))
ans += find(aib[i], 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], n;
Punct P[N];
Aib A;
ifstream in("zoo.in");
ofstream out("zoo.out");
int norm(int x){
int ans = 0;
for (int step = 1 << 13 ; step ; step >>= 1)
if ( (ans ^ step) <= X[0] && X[ans ^ step] <= x )
ans ^= step;
return ans;
}
int main(){
int x, y, z, t, nrQ;
in >> n;
for (int i = 1 ; i <= n ; i++)
in >> P[i].x >> P[i].y;
sort(P + 1, P + n + 1);
X[0] = 1;
X[1] = P[1].x;
for (int i = 2 ; i <= n ; i++)
if (P[i].x != X[ X[0] ])
X[ ++X[0] ] = P[i].x;
A.init(X[0]);
for (int i = 1 ; i <= n ; i++)
A.insert( norm(P[i].x), P[i].y );
in >> nrQ;
while (nrQ--){
in >> x >> y >> z >> t;
out << A.query( norm(x - 1), y - 1, norm(z), t ) << "\n";
}
return 0;
}