Cod sursa(job #60542)

Utilizator floringh06Florin Ghesu floringh06 Data 15 mai 2007 08:07:59
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.27 kb
// complexitate ~ n log n solutie greedy

using namespace std;

#define nmax 100005
#define INFTY 0x3f3f3f3f
#define max2(a,b) (a)>(b)?(a):(b)


#include<iostream>
#include<stdio.h>
#include<stdlib.h>

FILE *fin=fopen("lupu.in","r"),
     *fout=fopen("lupu.out","w");
     
struct date {int d; int l; int t;};     

struct nod {int info; nod*st,*dr;int hi;};
     
int tmax,sol;     
date a[nmax];

//bijuterie de AVL :)

int minim(nod *p)
 { if (p->st!=NULL) return minim(p->st);
   else return p->info;
 }

int maxim(nod *p)
 {
   if (p->dr!=NULL) return maxim(p->dr);
     else return p->info;
 }

int ad(nod*p)
{  if (p!=NULL) return p->hi; else return -1; }

void rotate_right(nod *&x)
{ 
  nod *y, *aux;
  y = x->st; aux = y->dr;
  y->dr=x; x->st=aux;
  x->hi = 1+max2(ad(x->st), ad(x->dr));
  y->hi = 1+max2(ad(y->st), ad(y->dr));
  x = y;
}

void rotate_left(nod *&y)
{ 
  nod *x, *aux;
  x = y->dr; aux = x->st;
  x->st=y; y->dr=aux;
  y->hi = 1+max2(ad(y->st), ad(y->dr));
  x->hi = 1+max2(ad(x->st), ad(x->dr));
  y = x;
}
void drotate_right(nod *&x)
 { 
   rotate_right(x->dr);
   rotate_left(x);
  }
void drotate_left(nod*&x)
{ 
  rotate_left(x->st);
  rotate_right(x);
}
void ins(nod*&p, int val)
{ if (p==NULL)
   { p = new nod;
     p->st=p->dr=NULL;
     p->hi=0;
     p->info = val;
     return;
    }
  if (val<p->info)
   { ins(p->st,val);
     if (ad(p->st)-ad(p->dr)>=2)
       if (ad(p->st->st) > ad(p->st->dr))   rotate_right(p);
        else  drotate_right(p);
      else p->hi = 1+max2(ad(p->st), ad(p->dr));
     }
   else
    if (val>p->info)
      { ins(p->dr,val);
        if (ad(p->dr)-ad(p->st)>=2)
          if (ad(p->dr->dr) > ad(p->dr->st)) rotate_left(p);
          else drotate_left(p);
          else p->hi = 1+max2(ad(p->st), ad(p->dr));
      }
}

void del(nod *&p,int val)
{ if (p==NULL) { cout<<"nu e"; return;}
  if (p->info == val)
    { if (p->st == NULL)
      {nod*temp = p->dr;
       delete p;
       p = temp;
       return;
       }
      if (p->dr == NULL)
       {
        nod*temp = p->st;
        delete p;
        p = temp;
        return;
        }
       int temp = minim(p->dr);
       p->info = temp;
       del(p->dr,temp);
        if (ad(p->st)-ad(p->dr)>=2)
          if (ad(p->st->st) > ad(p->st->dr))
            rotate_right(p);
           else
            drotate_right(p);
        else
          p->hi = 1+max2(ad(p->st), ad(p->dr));
       return;
      }
     if (val>p->info)
      { del(p->dr,val);
        if (ad(p->st)-ad(p->dr)>=2)
          if (ad(p->st->st) > ad(p->st->dr))
            rotate_right(p);
          else
            drotate_right(p);
         else
            p->hi = 1+max2(ad(p->st), ad(p->dr));
        }
       else
      { del(p->st,val);
        if (ad(p->dr)-ad(p->st)>=2)
          if (ad(p->dr->dr) > ad(p->dr->st))
            rotate_left(p);
          else
            drotate_left(p);
          else
            p->hi = 1+max2(ad(p->st), ad(p->dr));
       }
}    
int N,i,X,L;

//bagam sort - reducem cautarea din n^2 la n log n

void part(int st,int dr, int &stst, int &stdr, int &drst, int &drdr)
 {
  int i,j,piv; date aux;
  piv=a[(st+dr)/2].t; i=st-1; j=dr+1;
  while (i<j){ do {i++;} while (a[i].t>piv);
  do {j--;} while (a[j].t<piv);
   if (i<j) { aux=a[i]; a[i]=a[j]; a[j]=aux; } }
  stst=st; drdr=dr; if (i==j) { stdr=j-1; drst=i+1; }
  else { stdr=j; drst=i; } }

 void sort(int st, int dr)
 { int stst,stdr,drst,drdr;
   if (st<dr) { part(st,dr,stst,stdr,drst,drdr);
   sort(stst,stdr); sort(drst,drdr);  } }

int pp,j,vl;

int main()
{
   nod*root=NULL;
   fscanf(fin,"%d%d%d\n",&N,&X,&L);
   tmax=-INFTY;
   for (i=1; i<=N; i++)
    {
     fscanf(fin,"%d%d\n",&a[i].d,&a[i].l);
     if (a[i].d<=X) {
       a[i].t=(X-a[i].d+L)/L;
       tmax=max2((X-a[i].d+L)/L,tmax);
       } else  { i--; N--; } 
    }
   sort(1,N); j=1;
   while (j<=N)
    {
      pp=a[j].t;
      ins(root,a[j].l);
      while (a[j+1].t==pp) {  j++; ins(root,a[j].l); } // totul intra in arbore
      vl=maxim(root); sol+=vl; //hopa...mai bagam un maxim la solutie
      del(root,vl); j++;
    }
   fprintf(fout,"%d\n",sol); //voila ...:P si solutia
   fclose(fin); fclose(fout);  
   return 0;
}