Cod sursa(job #966327)

Utilizator harungunaydin313123 harungunaydin Data 25 iunie 2013 18:44:26
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#define FOR(i,a,b) for(i=a; i<=b; i++)
#define FOR2(i,n) FOR(i,0,n-1)
#define all(x) x.begin(),x.end()
#define MAXN 1000005
using namespace std;
class Edge
{
	public:
		int k,x,y1,y2;
		void set(int a,int b1,int b2,int z) { x = a; y1 = b1; y2 = b2; k = z; }
}E[MAXN];
bool cmp( const Edge &a , const Edge &b )
{
	if(a.x < b.x) return 1;
	if(a.x > b.x) return 0;
	return a.k == 2;
}
int F[MAXN];
void update(int a,int b,int k)
{
	int i;
	for(i = a; i < MAXN; i+=i&-i) F[i] += k;
	for(i = b + 1; i < MAXN; i += i&-i) F[i] -= k;
}
int find(int a)
{
	int i,s(0);
	for(i = a; i ; i -= i&-i) s += F[i];
	return s;
}
int M,N,H,S,W;
void solve()
{
	int a,b,i,res(0);
	scanf("%d %d %d %d",&N,&M,&W,&H);
	
	FOR(i,1,N)
	{
		scanf("%d %d",&a,&b);
		a++; b++;
		E[++S].set(a,b,b+H-1,0);
		E[++S].set(a+W-1,b,b+H-1,1);
	}
	FOR(i,1,M)
	{
		scanf("%d %d",&a,&b);
		a++; b++;
		E[++S].set(a,b,b,2);
	}
	sort(E+1,E+S+1,cmp);

	FOR(i,1,S)
	{
		if(!E[i].k) update(E[i].y1,E[i].y2,1);
		else if(E[i].k == 1) update(E[i].y1,E[i].y2,-1);
		else if(find(E[i].y1)) res++;
	}

	printf("%d\n" , res );


}
int main()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	solve();
	return 0;
}