Pagini recente » Cod sursa (job #2273946) | Cod sursa (job #2223770) | Cod sursa (job #2750164) | Cod sursa (job #2553679) | Cod sursa (job #1233943)
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <cctype>
#define NMAX 16005
#define MMAX 100005
#define lsb(x) ((x)&(-x))
using namespace std;
int aib[16005];
int marime;
inline void update(int i){
for(;i<=marime;i+=lsb(i))
aib[i]++;
}
inline int query(int i){
int s=0;
for(;i;i-=lsb(i))
s+=aib[i];
return s;
}
int ans[MMAX];
//Parsare
/*
ifstream cin("zoo.in");
char sir[6496005];
int lung,poz;
inline void cit(){
cin.get(sir+1,6496005,'#');
lung=strlen(sir+1);
poz=1;
}
inline int extract(){
while(poz<=lung && (!isdigit(sir[poz]) && sir[poz]!='-'))
++poz;
int semn=1;
if(sir[poz]=='-'){
semn=-1;
++poz;
}
int rez=0;
while(poz<=lung && isdigit(sir[poz])){
rez*=10;
rez+=(sir[poz]-'0');
++poz;
}
return (semn*rez);
}*/
//End of Parsare
//Parsare2
class InputReader {
public:
InputReader() {}
InputReader(const char *file_name) {
input_file = fopen(file_name, "r");
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
inline InputReader &operator >>(int &n) {
while(!isdigit(buffer[cursor]) && buffer[cursor]!='-')
advance();
int sgn=1;
if(buffer[cursor]=='-'){
sgn=-1;
advance();
}
n = 0;
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
n = n * 10 + buffer[cursor] - '0';
advance();
}
n*=sgn;
return *this;
}
private:
FILE *input_file;
static const int SIZE = 1 << 22;
int cursor;
char buffer[SIZE];
inline void advance() {
++ cursor;
if(cursor == SIZE) {
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
}
};
//End of Parsare2
struct operatie
{
int x,y;
int tip;
int poz;
}op[NMAX+4*MMAX];
bool operator<(const operatie &a,const operatie &b){
if(a.x<b.x)
return 1;
if(a.x>b.x)
return 0;
return a.tip<b.tip;
}
InputReader cin("zoo.in");
int main()
{
//ios_base::sync_with_stdio(false);
//ifstream cin("zoo.in");
//ofstream cout("zoo.out");
ofstream cout("zoo.out");
vector<int> setx,sety;
int n=0;
//cit();
cin>>n;
//n=extract();
vector<int> verifx;
vector<int> verify;
//Normalizare
verifx.push_back(-2000000005);
verifx.push_back(2000000005);
verify.push_back(-2000000005);
verify.push_back(2000000005);
for(int i=1;i<=n;++i){
//cin>>x>>y;
//op[i].x=extract();
//op[i].y=extract();
cin>>op[i].x;
cin>>op[i].y;
op[i].poz=i;
//if(!verifx.count(op[i].x)){
verifx.push_back(op[i].x);
// verifx.insert(op[i].x);
//}
//if(!verify.count(op[i].y)){
verify.push_back(op[i].y);
// verify.insert(op[i].y);
//}
}
sort(verifx.begin(),verifx.end());
sort(verify.begin(),verify.end());
setx.push_back(verifx[0]);
sety.push_back(verify[0]);
for(int i=1;i<verifx.size();i++){
if(verifx[i]!=verifx[i-1])
setx.push_back(verifx[i]);
if(verify[i]!=verify[i-1])
sety.push_back(verify[i]);
}
for(int i=1;i<=n;++i){
op[i].x=lower_bound(setx.begin(),setx.end(),op[i].x)-setx.begin()+1;
op[i].y=lower_bound(sety.begin(),sety.end(),op[i].y)-sety.begin()+1;
}
//End of Normalizare
int m=0;
cin>>m;
//m=extract();
int x1,y1,x2,y2;
int poz=n;
for(int i=1;i<=m;++i){
cin>>x1>>y1>>x2>>y2;
//x1=extract();
//y1=extract();
//x2=extract();
//y2=extract();
x1=lower_bound(setx.begin(),setx.end(),x1)-setx.begin();
x2=upper_bound(setx.begin(),setx.end(),x2)-setx.begin();
y1=lower_bound(sety.begin(),sety.end(),y1)-sety.begin();
y2=upper_bound(sety.begin(),sety.end(),y2)-sety.begin();
//assert(y1 && y1 && x1 && x2);
if(y1<=y2 && x1<=x2){
//cout<<query(y1,y2,1,x2-1)-query(y1,y2,1,x1-1)<<'\n';
op[++poz].poz=i;
op[poz].tip=1;
op[poz].x=x2;
op[poz].y=y2;
op[++poz].poz=i;
op[poz].tip=1;
op[poz].x=x1;
op[poz].y=y1;
op[++poz].poz=i;
op[poz].tip=2;
op[poz].x=x1;
op[poz].y=y2;
op[++poz].poz=i;
op[poz].tip=2;
op[poz].x=x2;
op[poz].y=y1;
}
}
sort(op+1,op+poz+1);
marime=sety.size();
for(int i=1;i<=poz;++i)
if(!op[i].tip)
update(op[i].y);
else if(op[i].tip==1)
ans[op[i].poz]+=query(op[i].y);
else
ans[op[i].poz]-=query(op[i].y);
for(int i=1;i<=m;++i)
cout<<ans[i]<<'\n';
//cin.close();
//cout.close();
return 0;
}