Pagini recente » Cod sursa (job #1698291) | Cod sursa (job #2911208) | Cod sursa (job #1605537) | Cod sursa (job #1751709) | Cod sursa (job #2810197)
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ifstream f ("zoo.in");
ofstream g ("zoo.out");
int n;
struct punct
{
int y;
int x;
};
punct a[20005];
int cmp(punct A, punct B)
{
if(A.x<B.x)
return 1;
return 0;
}
struct query
{
int dr;
int jos;
int indice;
int semn;
};
punct qu[100005];
int cmp2(query A, query B)
{
if(A.dr<B.dr)
return 1;
return 0;
}
multiset <int> s;
query b[500005];
int cont=0;
int rasp[100005];
int q;
int main()
{
ios_base::sync_with_stdio(false);
f.tie(NULL);
f>>n;
for(int i=1; i<=n; ++i)
{
f>>a[i].x>>a[i].y;
}
sort(a+1, a+n+1, cmp);
f>>q;
for(int i=1; i<=q; ++i)
{
int A,B,C,D;
f>>B>>A>>D>>C;
query x;
x.dr=D;
x.jos=A;
x.indice=i;
x.semn=1;
b[++cont]=x;
x.dr=B-1;
x.jos=C+1;
x.indice=i;
x.semn=1;
b[++cont]=x;
x.dr=B-1;
x.jos=A;
x.indice=i;
x.semn=-1;
b[++cont]=x;
x.dr=D;
x.jos=C+1;
x.indice=i;
x.semn=-1;
b[++cont]=x;
}
sort(b+1, b+cont+1, cmp2);
int pctcur=1;
for(int i=1; i<=cont; ++i)
{
int limdr=b[i].dr;
while(a[pctcur].x<=b[i].dr && pctcur<=n)
{
s.insert(a[pctcur].y);
++pctcur;
}
int r=distance(s.begin(), s.lower_bound(b[i].jos));
rasp[b[i].indice]+=(pctcur-r-1)*b[i].semn;
}
for(int i=1; i<=q; ++i)
g<<rasp[i]<<"\n";
return 0;
}