Cod sursa(job #1848669)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 16 ianuarie 2017 14:02:16
Problema Lupul Urias si Rau Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <fstream>
#include <algorithm>
#define LMAX 100001

using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");

struct oaie{
    int tura;
    int lana;
};oaie o[LMAX];

int H[LMAX];
int n, L, x;
int lg;
int afisez;

void citire();
void sortare();
void rezolvare();
void afisare();

void inserare(int x);
void combinare(int i);
void creare();
int extragere_max();

bool criteriu(oaie a, oaie b);

int main()
{
citire();
sortare();
rezolvare();
afisare();
fin.close();
fout.close();
return 0;
}

void citire()
    {
     int i, d;
     fin>>n>>x>>L;
     for (i=1;i<=n;i++)
         {
          fin>>d>>o[i].lana;
          o[i].tura=(x-d)/L+1;
         }
     n++;
     lg=n;
    }

void sortare()
    {
     sort (o+1, o+n+1, criteriu);
    }

bool criteriu(oaie a, oaie b)
    {
     return a.tura>b.tura;
    }

void rezolvare()
    {
     int i;
     int tura=o[1].tura;
     int ultim;
     int dif;
     for (i=1;1;i++)
          if (o[i].tura==tura)
              inserare(o[i].lana);
              else
              break;
     ultim=tura;
     n=i-1;
     while (i<=lg)
         {
          tura=o[i].tura;
          dif=ultim-tura;
          while (dif>0)
             {
              afisez+=extragere_max();
              dif--;
             }
          for (;i<=lg;i++)
               if (o[i].tura==tura)
                   inserare(o[i].lana);
                   else break;
          ultim=tura;
         }
    }

void combinare(int i)
    {
     //combin nodul H[i] cu heapurile cu radacinile H[2*i] si H[2*i+1]
     int x=H[i], tata=i, fiu;
     while (1)
        {
         fiu=2*tata;
         if (fiu>n)
             break;
         if (fiu+1<=n&&H[fiu+1]>H[fiu])
             fiu++;
         if (H[fiu]<=x)
             break;
         H[tata]=H[fiu];
         tata=fiu;
        }
     H[tata]=x;
    }

void creare()
    {
     int i;
     for (i=n/2;i>0;i--)
          combinare(i);
    }

int extragere_max()
    {
     if (n==0)
         return 0;
     int maxim=H[1];
     H[1]=H[n--];
     combinare(1);
     return maxim;
    }

void inserare(int x)
    {
     int fiu=++n;
     int tata=fiu/2;
     while (tata && H[tata]<x)
           {
            H[fiu]=H[tata];
            fiu=tata;
            tata=fiu/2;
           }
     H[fiu]=x;
    }

void afisare()
    {
     fout<<afisez<<'\n';
    }