Pagini recente » Cod sursa (job #935960) | Cod sursa (job #2857813) | Cod sursa (job #1012751) | Cod sursa (job #3258132) | Cod sursa (job #2882375)
#include <bits/stdc++.h>
#define nmax 16005
#define mmax 100005
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
int p=0;
int queries[mmax];
int arb[(mmax*2+nmax)];
int n,m;
int ind;
struct punct
{
int x,y,queryid;
bool query,op;
punct(int x=0,int y=0,bool query=0,int queryid=0,bool op=0)
{
this->x=x;
this->y=y;
this->query=query;
this->queryid=queryid;
this->op=op;
}
bool operator <(const punct other)
{
if(x!=other.x)return x<other.x;
return !query;
}
void output()
{
out<<x<<' '<<y<<' '<<query<<' '<<queryid<<' '<<op<<'\n';
}
}puncte[mmax*4+nmax+5];
bool cmp(const punct a,const punct b)
{
return a.y<b.y;
}
void update(int x)
{
while(x<=ind)
{
arb[x]++;
x+=(x&(-x));
}
}
int q(int x)
{
int res=0;
while(x)
{
res+=arb[x];
x-=(x&(-x));
}
return res;
}
void normalizey()
{
sort(puncte,puncte+p,cmp);
for(int i=0;i<p;i++)
{
int val=puncte[i].y;
puncte[i].y=ind;
if(val<puncte[i+1].y)ind++;
}
}
int main()
{
in>>n;
for(int i=0;i<n;i++)
{
int x,y;
in>>x>>y;
puncte[p++]=punct(x,y);
}
in>>m;
for(int i=1;i<=m;i++)
{
int x1,y1,x2,y2;
in>>x1>>y1>>x2>>y2;
puncte[p++]=punct(x1-1,y1-1,1,i,0);
puncte[p++]=punct(x2,y2,1,i,0);
puncte[p++]=punct(x1-1,y2,1,i,1);
puncte[p++]=punct(x2,y1-1,1,i,1);
}
normalizey();
sort(puncte,puncte+p);
for(int i=0;i<p;i++)
{
if(!puncte[i].query)
{
update(puncte[i].y);
}
else
{
if(puncte[i].op)
{
queries[puncte[i].queryid]-=q(puncte[i].y);
}
else
{
queries[puncte[i].queryid]+=q(puncte[i].y);
}
}
}
for(int i=1;i<=m;i++)
{
out<<queries[i]<<'\n';
}
}