Cod sursa(job #305881)

Utilizator alex23alexandru andronache alex23 Data 18 aprilie 2009 19:50:15
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.05 kb
#include <iostream>

FILE *f = fopen("heavymetal.in", "r"), *g = fopen("heavymetal.out", "w");

using namespace std;

int *a, *b, *heapA, *heapB, N, *timp, *maxim;

int swap(int k, int p)
{
    int aux = heapA[k];
    heapA[k] = heapA[p];
    heapA[p] = aux;
    aux = heapB[k];
    heapB[k] = heapB[p];
    heapB[p] = aux;
    
    return 0;
}

int addHeap(const int x, const int y, int k)
{
    heapA[k] = x;
    heapB[k] = y;
    while (heapB[(k - 1) / 2] > heapB[k])
    {
          swap(k, (k - 1) / 2);
          k = (k - 1) / 2;
    } 
    return 0;
}

int deleteHeap(int k)
{
    a[k] = heapA[0];
    b[k] = heapB[0];
    int nrElemente = N - 1 - k;
    heapA[0] = heapA[nrElemente];
    heapB[0] = heapB[nrElemente];
    nrElemente--;
    k = 0;
    while ((2 * k + 2 <= nrElemente) && ((heapB[k] > heapB[2 * k + 1]) || (heapB[k] > heapB[2 * k + 2])))
    {
          if ((heapB[k] > heapB[2 * k + 1]) && (heapB[k] > heapB[2 * k + 2]))
          {
             if (heapB[2 * k + 1] > heapB[2 * k + 2])
             {
                swap(k , 2 * k + 2);
                k = 2 * k + 2;
             }
             else
             {
                 swap(k, 2 * k + 1);
                 k = 2 * k + 1; 
             }
          }
          else
          {
              if (heapB[k] > heapB[2 * k + 1])
              {
                 swap(k, 2 * k + 1);
                 k = 2 * k + 1;
              }
              else
              {
                  swap(k, 2 * k + 2);
                  k = 2 * k + 2;
              }
          }
    }
    if ((2 * k + 1 <= nrElemente) && (heapB[k] > heapB[2 * k + 1]))
    {
           swap(k, 2 * k + 1);
    }
    return 0;
}

int cautareBinara(int total, int val)
{
    int li = 0, ls = total;
    while (li < ls)
    {
          int m = (li + ls) / 2;
          if (timp[m] == val)
          {
             return maxim[m]; 
          }
          else
          {
              if (timp[m] < val)
              {
                 li = m + 1;
              }
              else
              {
                 ls = m - 1;
              }
          }
    }
    if (timp[li] == val) return maxim[li];
    if (timp[li] < val) return maxim[li + 1];
    if (timp[li] > val) return maxim[li - 1];
}

int main()
{
    fscanf(f, "%d", &N);
    a = new int[N];
    b = new int[N];
    heapA = new int[N];
    heapB = new int[N];
    for (int i = 0; i < N; ++i)
    {
        int x, y;
        fscanf(f, "%d %d", &x, &y);
        addHeap(x, y, i);
    }
    fclose(f);
    
    for (int i = 0; i < N; ++i)
    {
        deleteHeap(i);
    }
    delete[] heapA;
    delete[] heapB;
    
    timp = new int[N];
    maxim = new int[N];
    
    int j = 0, m = 0;
    while (a[j] == a[0])
    {
          if (m < b[j] - a[j])
          {
                m = b[j] - a[j];
          }
          j++;
    }
    int nr = 0; // numarul de elemente din timp si max;
    timp[nr] = a[0];
    maxim[nr] = m;
    for (int i = j; i < N; ++i)
    {
        if (a[i] < timp[0])
        {
            if (timp[nr] != b[i])
            {
                timp[++nr] = b[i];
                maxim[nr] = b[i] - a[i];
            }
            else
            {
                if (maxim[nr] < b[i] - a[i])
                {
                    maxim[nr] = b[i] - a[i];
                }
            }
        }
        else
        {
            int t = cautareBinara(nr, a[i]); //returneaza val maxima a timpului cel mai apropiat de a[i]
            if (timp[nr] != b[i])
            {
               timp[++nr] = b[i];
               maxim[nr] = t + b[i] - a[i];
            }
            else
            {
                if (maxim[nr] < b[i] - a[i] + t)
                {
                   maxim[nr] = b[i] - a[i] + t;
                }
            }
        }
    } 
    
    fprintf(g, "%d", maxim[nr]);
    fclose(g);
    
    delete[] timp;
    delete[] maxim;
    
    delete[] a;
    delete[] b;
    
    return 0;
}