Cod sursa(job #769131)

Utilizator ion824Ion Ureche ion824 Data 18 iulie 2012 13:57:42
Problema Lupul Urias si Rau Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream>
#include<algorithm>
using namespace std;
const int NM = 100005;
int d[NM],ln[NM],t[NM],I[NM];
int h[NM],poz[NM],v[NM],hp,n;

inline void swap(int &a,int &b){ int k=a; a=b; b=k; }

struct cmp{
  bool operator()(const int &i,const int &j){
       return t[i]>t[j];
       }       
};

void upheap(int k){
    while(k>1 && v[h[k]]>v[h[k/2]])
     {
      swap(poz[h[k]],poz[h[k/2]]);
      swap(h[k],h[k/2]);
      k/=2;
     }              
}

void downheap(int k){
     int nod=1;
     while(nod)
      {
       nod=0;
       if(2*k<=hp)
        {
          nod=2*k;
          if(2*k+1<=hp && v[h[nod]]<v[h[nod+1]])++nod;         
          if(v[h[nod]]<=v[h[k]])nod=0;
        }          
        if(nod)
         {
          swap(poz[h[nod]],poz[h[k]]);
          swap(h[nod],h[k]);
          k=nod;      
         }                        
      }               
}

void insert(int k){
     v[++n]=k; h[++hp]=n; poz[n]=hp;
     upheap(hp);
}

void del(int k){
     poz[h[hp]]=k; swap(h[k],h[hp]); --hp;
     if(k>1 && v[h[k]]>v[h[k/2]])upheap(k);
       else downheap(k);
}

int main(void){
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    int N,L,X,i,j,tmax=0,x; long long cost=0;
    fin>>N>>X>>L;
    for(i=1;i<=N;++i)
      {
       fin>>d[i]>>ln[i];
       t[i]=(X-d[i])/2+1;
       if(t[i]>tmax)tmax=t[i];
       I[i]=i;               
      }
    sort(I+1,I+N+1,cmp());
    j=tmax; i=1;
    while(j>0)
    {
       while(t[I[i]]==j && i<=N){ insert(ln[I[i]]); ++i; }       
       if(hp)
         {
          cost+=v[h[1]];
          del(poz[v[h[1]]]);    
         }  
      --j;             
    }
    fout<<cost<<'\n';             
 return 0;   
}