Pagini recente » Cod sursa (job #1177431) | Cod sursa (job #3277592) | Cod sursa (job #654447) | Cod sursa (job #1206054) | Cod sursa (job #2496104)
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w,h,rmq[30][50005];pair <int,int> v[50003];
int cb1 (int nr) {
int i=0,step=1;
for(;(step<<1)<=n;step=(step<<1));
for(;step>0;step=(step>>1))
if(i+step<=n && v[i+step].first+w<nr)
i+=step;
return i;
}
int cb2 (int nr) {
int i=0,step=1;
for(;(step<<1)<=n;step=(step<<1));
for(;step>0;step=(step>>1))
if(i+step<=n && v[i+step].first+w<=nr)
i+=step;
return i;
}
void rmq1 () {
for(int i=1;i<=n;++i)
rmq[0][i]=v[i].second;
for(int i=1;i<=27;++i)
for(int j=1;j<=n;++j)
if(((j+1)<<i)<=n)
rmq[i][j]=max(rmq[i-1][j],rmq[i-1][((j+1)<<(i-1))]);
}
int main () {
int nr1,nr2,kontor=0,poz1,poz2,logi,dif;
freopen("ograzi.in","r",stdin);
freopen("ograzi.out","w",stdout);
scanf("%d%d%d%d", &n, &m, &w, &h);
for(int i=1;i<=n;++i) {
scanf("%d%d", &nr1, &nr2);
v[i].first=nr1;v[i].second=nr2;
}
sort(v+1,v+n+1);
rmq1();
for(int i=1;i<=m;++i) {
scanf("%d%d", &nr1, &nr2);
//poz[nr1].push_back(nr2);
poz1=cb1(nr1)+1;poz2=cb2(nr1);dif=poz2-poz1;
logi=0;
for(int i=0;dif>0;++i)
if((dif & (1<<i))!=0)
logi=i,dif-=(1<<i);
if(max(rmq[logi][poz1],rmq[logi][poz2-(1<<logi)])<=nr2)
++kontor;
}
printf("%d", kontor);
return 0;
// fac un rmq pentru maximul pe intervale ;
}