Translate

miércoles, 14 de diciembre de 2011

Problema Army buddies (Intervar Tree)


Problema Army buddies

Este problema es del regional Mexico Centro America y el caribe: 

http://coj.uci.cu/24h/problem.xhtml?abb=1581


/* Autor: Rodrigo Burgos Dominguez */

# include "stdio.h"
# include "string.h"

typedef struct { int izq, der, cont;  } TREE;

TREE MEM[1000000];

int s, b, nmem;
int delete(int *pt, int A, int B, int L, int R){
  int sum, med;
  if( B < L || A > R){
    return *pt == -1 ? (B - A + 1)  : MEM[*pt].cont;
  }
  if( *pt != -1 && MEM[*pt].cont == 0 ) return 0; 
  if( *pt == -1 ){
   *pt = nmem++;
    MEM[ *pt ].izq = -1;
    MEM[ *pt ].der = -1;
    MEM[ *pt ].cont = B - A + 1;
  }
  if( A >= L && B <= R ){
     MEM[*pt].cont = 0;
      return 0; 
  }
  med = (A + B) / 2;
  sum  = delete( &MEM[ *pt].izq, A, med, L, R);
  sum += delete( &MEM[ *pt].der, med+1, B, L, R);
  MEM[*pt].cont = sum;
  return sum;
}

int find( int pt, int A, int B, int pos, int dir){
   int med = (A + B) / 2, r;
   if( pos == 0 ) return 0;
   if( pt != -1 && MEM[pt].cont == 0  ) return 0;
   if( dir >= 1 ){
     if( B < pos ) return 0;
     if( pt == -1 ){
      if( pos >= A && pos <= B ) return pos;
      return A;
     }
     r = find( MEM[pt].izq, A, med, pos, dir);
     if( r > 0 ) return r;
     r = find( MEM[pt].der, med +1, B , pos, dir);
     if( r > 0 ) return r;
   }else {
    if( A > pos ) return 0;
     if( pt == -1 ){
      if( pos >= A && pos <= B ) return pos;
      return B;
     }
     r = find( MEM[pt].der, me` +1, B , pos, dir);
     if( r > 0 ) return r;
     r = find( MEM[pt].izq, A, med, pos, dir);
     if( r > 0 ) return r;
   } 
   return 0;
}

main(){
  int indice, q, l, r, A, B;
  while( scanf("%d %d", &s, &b) != EOF && ( s || b )) {
   indice = -1;
   nmem = 0;
   for( q = 0; q < b; q++){
      scanf("%d %d", &aip;l, &r);
      delete(&indice, 1, s, l, r);
      A  =  find(indice,  1, s, l-1, -1);
      B  =  find(indice,  1, s, r+1, +1);
      if( A == 0 ) printf("* ");
      else printf("%d ", A);
      if( B == 0 ) printf("*\n");
      else printf("%d\n", B);
   }
   printf("-\n");
  }
  return 0; 
}
   

No hay comentarios: