Pagini recente » Cod sursa (job #2453173) | Cod sursa (job #398452) | Cod sursa (job #1983406) | Cod sursa (job #2978429) | Cod sursa (job #3351001)
#include <fstream>
#include <utility>
#define x first
#define y second
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
typedef pair <int, int> pii;
const int nmax = 16000, qmax = 2e5;
int n, nrq, xx, yy, lff, rgg, answer[qmax + 2]; pii a[nmax + 2];
/// ---> normalize by y to have fenwick tree over points <--- ///
pii norm[nmax + 2]; int actually[nmax + 2], nvs;
void getnormalizedy(){
for(int i = 1; i <= n; i++){
norm[i] = make_pair(a[i].y, i);
}
norm[0].x = (1 << 31) + 1;
sort(norm + 1, norm + 1 + n);
for(int i = 1; i <= n; i++){
nvs += (norm[i].x != norm[i - 1].x);
actually[nvs] = norm[i].x; a[norm[i].y].y = nvs;
}
return;
}
int getlefttpointt(int xx){
int st = 1, dr = nvs, mij, bestt = -1;
for(; st <= dr; ){
mij = (st + dr) >> 1;
if(xx <= actually[mij]){
bestt = mij, dr = mij - 1;
}else{ st = mij + 1; }
}
return bestt;
}
int getrighttpointt(int xx){
int st = 1, dr = nvs, mij, bestt = -1;
for(; st <= dr; ){
mij = (st + dr) >> 1;
if(actually[mij] <= xx){
bestt = mij, st = mij + 1;
}else{ dr = mij - 1; }
}
return bestt;
}
struct query{
int heightt, leftt, rightt, qidx, sign;
query(int hh, int lff, int rgg, int idx, int sgn) :
heightt(hh), leftt(lff), rightt(rgg), qidx(idx), sign(sgn) {};
bool operator < (const query &obj) const {
return heightt < obj.heightt;
}
}; vector <query> queries;
inline int f(int x){ return (x & (-x)); }
struct fenwicktree{
int tree[nmax + 2];
void updateadd(int node, int vall){
for(int i = node; i <= nvs; i += f(i)){
tree[i] += vall;
}
return;
}
int query(int node){
int summ = 0;
for(int i = node; i >= 1; i -= f(i)){
summ += tree[i];
}
return summ;
}
} myaib;
int main(){
in>>n;
for(int i = 1; i <= n; i++){
in>>a[i].x>>a[i].y;
}
getnormalizedy();
in>>nrq; queries.reserve(2 * nrq);
for(int itq = 1; itq <= nrq; itq++){
in>>xx>>lff>>yy>>rgg;
lff = getlefttpointt(lff);
rgg = getrighttpointt(rgg);
if(lff == -1 || rgg == -1){ continue; }
queries.push_back(query(xx - 1, lff, rgg, itq, -1));
queries.push_back(query(yy, lff, rgg, itq, +1));
}
sort(queries.begin(), queries.end());
sort(a + 1, a + 1 + n); ///sweep line
int idx = 1;
for(auto qry : queries){
for(; idx <= n && a[idx].x <= qry.heightt; ){
myaib.updateadd(a[idx].y, +1); idx++;
}
answer[qry.qidx] -= qry.sign * myaib.query(qry.leftt - 1);
answer[qry.qidx] += qry.sign * myaib.query(qry.rightt);
}
for(int itq = 1; itq <= nrq; itq++){
out<<answer[itq]<<"\n";
}
return 0;
}