Pagini recente » Cod sursa (job #102653) | Cod sursa (job #2364693) | Cod sursa (job #2842653) | Cod sursa (job #2927344) | Cod sursa (job #3183886)
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
const int NMAX=16e3+5;
const int MMAX=1e5+5;
struct eventz{
int type; ///-1 capst, 0 point, 1 capdr
int x1;
int y1;
int x2;
int y2;
int ind;
}events[NMAX+2*MMAX];
int aib[NMAX];
int v[NMAX];
int norm[NMAX];
int ans[NMAX];
int xx[NMAX+2*MMAX];
int yy[NMAX+2*MMAX];
bool cmp(eventz a,eventz b)
{
if(a.x1==b.x1)
{
if(a.type==b.type)
return a.y1<b.y1;
else
return a.type<b.type;
}
return a.x1<b.x1;
}
int n;
int saiz;
int lsb(int x)
{
return x&(-x);
}
void update(int p,int val)
{
while(p<=saiz)
{
aib[p]+=val;
p+=lsb(p);
}
}
int query(int p)
{
int s=0;
while(p>0)
{
s+=aib[p];
p-=lsb(p);
}
return s;
}
int normalizare1(int x)
{
int st=1,dr=saiz,mij;
while(st<=dr)
{
mij=st+dr;
mij/=2;
if(xx[mij]<x)
st=mij+1;
else if(xx[mij]>x)
dr=mij-1;
else
return mij;
}
return st;
}
int normalizare2(int x)
{
int st=1,dr=saiz,mij;
while(st<=dr)
{
mij=st+dr;
mij/=2;
if(yy[mij]<x)
st=mij+1;
else if(yy[mij]>x)
dr=mij-1;
else
return mij;
}
return st;
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
int i,q;
fin>>n;
for(i=1;i<=n;i++)
{
int x,y;
fin>>x>>y;
events[++saiz]={0,x,y,0,0,0};
xx[saiz]=x;
yy[saiz]=y;
}
fin>>q;
for(i=1;i<=q;i++)
{
int x1,y1,y2,x2;
fin>>x1>>y1>>x2>>y2;
events[++saiz]={-1,x1,y1,x1,y2,i};
xx[saiz]=x1;
yy[saiz]=y1;
events[++saiz]={1,x2,y1,x2,y2,i};
xx[saiz]=x2;
yy[saiz]=y2;
}
sort(xx+1,xx+saiz+1);
sort(yy+1,yy+saiz+1);
for(i=1;i<=saiz;i++)
{
events[i].x1=normalizare1(events[i].x1);
events[i].x2=normalizare1(events[i].x2);
events[i].y1=normalizare2(events[i].y1);
events[i].y2=normalizare2(events[i].y2);
}
sort(events+1,events+saiz+1,cmp);
for(i=1;i<=saiz;i++)
{
if(events[i].type==0)
update(events[i].y1,1);
else if(events[i].type==-1)
ans[events[i].ind]-=query(events[i].y2)-query(events[i].y1-1);
else
ans[events[i].ind]+=query(events[i].y2)-query(events[i].y1-1);
}
for(i=1;i<=q;i++)
fout<<ans[i]<<"\n";
fin.close();
fout.close();
return 0;
}