Pagini recente » Cod sursa (job #1362267) | Cod sursa (job #152407) | Cod sursa (job #622065) | Cod sursa (job #2217804) | Cod sursa (job #1154115)
#include<stdio.h>
#include<algorithm>
#include<vector>
const int M=100001, N=16001;
using namespace std;
FILE *f,*g;
int x[2][N], xy[2][N]; int n,nr[2];
vector<int> valori[N]; //doar vactorul valori va fi folosit, restul sunt yedek
struct nod{
int y,rasp;
bool ok;
};
vector<nod> forquery[N]; int m;
int aib[N], intrb[M];
void read(void){
f=fopen("zoo.in","r");
g=fopen("zoo.out","w");
fscanf(f,"%d",&n);
int i;
for(i=1;i<=n;i++) fscanf(f,"%d%d",&xy[0][i],&xy[1][i]);
}
void sortare(void){
int i;
for(i=1; i<=n; i++) {x[0][i]=xy[0][i]; x[1][i]=xy[1][i]; }
sort(x[0]+1, x[0]+n+1);
sort(x[1]+1, x[1]+n+1);
int i1,i2;
i1=1;
for(i2=2;i2<=n;i2++){
if (x[0][i2] != x[0][i1]) x[0][++i1]=x[0][i2];
}
nr[0]=i1;
i1=1;
for(i2=2;i2<=n;i2++)
if (x[1][i2] != x[1][i1]) x[1][++i1]=x[1][i2];
nr[1]=i1;
}
int binsearch(int a, int b){
if (a<x[b][1]) return 0;
else if (a>=x[b][nr[b]]) return nr[b];
else {
int l=1, r=nr[b], mid;
while(r-l>1){
mid=(l+r)/2;
if (a < x[b][mid]) r=mid;
else l=mid;
}
return l;
}
}
void makegraph(void){
int i;
for(i=1;i<=n;i++) valori[binsearch(xy[0][i],0)].push_back(binsearch(xy[1][i],1));
}
void preambulquery(void){
fscanf(f,"%d",&m);
int i; int a,b,c,d; nod dumm;
for(i=1;i<=m;i++){
fscanf(f,"%d%d%d%d",&a,&b,&c,&d);
int ay=binsearch(a-1,0), cy=binsearch(c,0);
dumm.y=binsearch(b-1,1); dumm.rasp=i; dumm.ok=1;
forquery[ay].push_back(dumm);
dumm.ok=0;
forquery[cy].push_back(dumm);
dumm.y=binsearch(d,1);
forquery[ay].push_back(dumm);
dumm.ok=1;
forquery[cy].push_back(dumm);
}
}
int suc(int l){
return 2*l-(l&(l-1));
}
int pred(int l){
return l&(l-1);
}
void update(int l){
while (l <= nr[0]) {aib[l]++; l=suc(l); }
}
int query(int l){
int sum=0;
if (l)
while (l){
sum+=aib[l];
l=pred(l);
}
return sum;
}
void initline(int i){
vector<int>::iterator it=valori[i].begin();
while(it!=valori[i].end()){
update(*it);
it++;
}
}
void solveline(int i){
vector<nod>::iterator it=forquery[i].begin();
while (it != forquery[i].end() ){
if (it->ok) intrb[it->rasp] += query(it->y);
else intrb[it->rasp] -= query(it->y);
++it;
}
}
void solveall(void){
int i;
for(i=1; i<=nr[0]; i++) {initline(i); solveline(i); }
for(i=1; i<=m ;i++) fprintf(g,"%d\n",intrb[i]);
}
int main(void){
read();
sortare();
makegraph();
preambulquery();
solveall();
return 0;
}