Cod sursa(job #144282)

Utilizator gigi_becaliGigi Becali gigi_becali Data 27 februarie 2008 13:43:40
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
using namespace std;
#include <cstdio>
#include <string>
#include <algorithm>
#define bit(x) ( (x) & (((x)-1) ^(x)))
struct nod { int x, y, t;nod(){};nod(int a, int b, int c){x=a;y=b;t=c;};};

struct cmp{
  bool operator()(const nod &a, const nod &b)const
  {
    if(a.x<b.x)return 1;
    if(a.x==b.x && a.t<b.t) return 1;
    if(a.x==b.x && a.t==b.t &&  a.y<b.y)return 1;
    return 0;
  }
};

nod a[200001];
int N;
int aib[1000001];
int n, W, H,m;

inline void update(int x, int v)
{
  for(int i=x;i<=1000000; i+=bit(i))aib[i]+=v;
}

inline int query(int x)
{
  int s=0;
  for(int i=x; i>0;i-=bit(i)) s+=aib[i];
  if(s==0) return 0;
  return 1;
}



int main()
{
  freopen("ograzi.in","r",stdin);
  scanf("%d %d %d %d\n", &n, &m, &W, &H);

  int i,  x,y;

  for(i=1;i<=n;++i)
    {
      scanf("%d %d\n", &x, &y);
       ++x;++y;
      a[++N]=nod(x, y, 0);
      a[++N]=nod(x+W, y, 2);

    }


  for(i=1;i<=m;++i)
    {
      scanf("%d %d\n", &x, &y);
      ++x;++y;
      a[++N]=nod(x, y, 1);
    }

  sort(a+1,a+N+1,cmp());

  // for(i=1;i<=N;++i)printf("%d %d %d\n",a[i].x, a[i].y, a[i].t);

  int rez=0;
  for(i=1;i<=N;++i)
    {
      if(a[i].t==0) 
	{
	  update(a[i].y,1);
	  update(a[i].y+H,1);
	}

      if(a[i].t==2)
	{
	  update(a[i].y,-1);
	  update(a[i].y+H+1, -1);
	}

      if(a[i].t==1)
	{
	  rez+=query(a[i].y);
	} 
    }

  freopen("ograzi.out","w",stdout);
  printf("%d\n", rez/2);

  return 0;
}