Pagini recente » Cod sursa (job #2692664) | Cod sursa (job #2487037) | Cod sursa (job #1477907) | Cod sursa (job #2144091) | Cod sursa (job #2811219)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("zoo.in");
ofstream g ("zoo.out");
struct ceva
{
int x;
int y;
int indice;
int poznorm;
};
ceva a[500005];
struct qu
{
int dr;
int jos;
int indice;
int semn;
};
qu x;
int n;
int q;
int cmp (ceva A, ceva B)
{
if(A.y<=B.y)
return 1;
return 0;
}
ceva ajut[500005];
void chestie()
{
int val=0;
ajut[0].y=-INT_MAX;
for(int i=1; i<=n; ++i)
{
if(ajut[i].y!=ajut[i-1].y)
++val;
int ind=ajut[i].indice;
a[ind].y=val;
ajut[i].poznorm=val;
}
}
qu b[1000005];
int cb(int val)
{
int st=1;
int dr=n;
int mij=(st+dr)/2;
while(st<=dr)
{
if(ajut[mij].y<=val && ajut[mij+1].y>val)
return ajut[mij].poznorm;
if(ajut[mij].y>val)
dr=mij-1;
else
st=mij+1;
mij=(st+dr)/2;
}
return 0;
}
int aint[1000005];
void Update(int nod, int st, int dr, int val)
{
if(st==dr)
{
aint[nod]++;
return;
}
int mij=(st+dr)/2;
if(mij>=val)
{
Update(2*nod , st , mij , val);
aint[nod]=aint[2*nod]+aint[2*nod+1];
}
else
{
Update(2*nod+1 , mij+1 , dr , val);
aint[nod]=aint[2*nod]+aint[2*nod+1];
}
}
int Query(int nod , int st , int dr , int val)
{
if(st==dr)
{
return aint[nod];
}
int mij=(st+dr)/2;
if(val<=mij)
return Query(2*nod , st , mij , val);
else
return aint[2*nod]+Query(2*nod+1 , mij+1 , dr , val);
}
int cmp2(qu A, qu B)
{
if(A.dr<B.dr)
return 1;
return 0;
}
int rasp[500005];
int cont;
int cmp3(ceva A , ceva B)
{
if(A.x<B.x)
return 1;
return 0;
}
int main()
{
f>>n;
for(int i=1; i<=n; ++i)
{
f>>a[i].x;
f>>a[i].y;
a[i].indice=i;
ajut[i]=a[i];
}
ajut[n+1].y=INT_MAX;
sort(ajut+1, ajut+n+1, cmp);
chestie();
f>>q;
for(int i=1; i<=q; ++i)
{
int A,B,C,D;
f>>B>>A>>D>>C;
qu x;
x.dr=D;
x.jos=cb(A-1);
x.indice=i;
x.semn=-1;
b[++cont]=x;
x.dr=B-1;
x.jos=cb(C);
x.indice=i;
x.semn=-1;
b[++cont]=x;
x.dr=B-1;
x.jos=cb(A-1);
x.indice=i;
x.semn=1;
b[++cont]=x;
x.dr=D;
x.jos=cb(C);
x.indice=i;
x.semn=1;
b[++cont]=x;
}
sort(b+1, b+cont+1, cmp2);
sort(a+1 , a+n+1 , cmp3);
int bagate=1;
for(int i=1; i<=cont; ++i)
{
while(a[bagate].x<=b[i].dr && bagate<=n)
{
Update(1, 1, n, a[bagate].y);
++bagate;
}
int rez=0;
if(b[i].jos!=0)
rez=Query(1, 1, n, b[i].jos);
rasp[b[i].indice]+=rez*b[i].semn;
}
for(int i=1; i<=q; ++i)
g<<rasp[i]<<"\n";
return 0;
}