Cod sursa(job #2496110)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 20 noiembrie 2019 11:22:42
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda casiaiziscanudaisimulareprimaora Marime 1.31 kb
#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 ;
}