Cod sursa(job #144286)

Utilizator gigi_becaliGigi Becali gigi_becali Data 27 februarie 2008 13:47:09
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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[1000021];
int n, W, H,m;

inline void update(int x, int v)
{
  for(int i=x;i<=1000020; 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;
  char ax[32],*p;

  for(i=1;i<=n;++i)
    {
      //scanf("%d %d\n", &x, &y);
      gets(ax);
      p=strtok(ax, " ");
      x=atoi(p);
      p=strtok(0, "\n");
      y=atoi(p);
       ++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);
      gets(ax);
      p=strtok(ax, " ");
      x=atoi(p);
      p=strtok(0, "\n");
      y=atoi(p);
      ++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,-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);

  return 0;
}