Cod sursa(job #2513828)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 23 decembrie 2019 20:51:40
Problema Heavy metal Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int N;
struct concert{
    int A,B,val;
}v[100005];
int q[200005], d[100005], Tmax,Q,poz,rez;
map <int, int> M;
inline bool cmp(concert A, concert B){
    if(A.B==B.B)return A.A>B.A;
    else return A.B<B.B;
}
void CautBin(int st, int dr)
 {int mid=(st+dr)/2;
  if(st==dr) poz=mid;
  else {
    if(v[mid].B>=Q)CautBin(st,mid);
    else CautBin(mid+1,dr);
    }
 }
int main()
{fin>>N;
 for(int i=1;i<=N;i++){
     fin>>v[i].A>>v[i].B;
     q[i*2-1]=v[i].A;
     q[i*2]=v[i].B;
     v[i].val=v[i].B-v[i].A;
    }
 sort(q+1,q+2*N+1);
 for(int i=1;i<=2*N;i++){
     if(q[i]>q[i-1])M[q[i]]=M[q[i-1]]+1;
     else M[q[i]]=M[q[i-1]];
     Tmax=max(Tmax,M[q[i]]);
    }
 for(int i=1;i<=N;i++){
    v[i].A=M[v[i].A];
    v[i].B=M[v[i].B];
    }
  sort(v+1,v+N+1,cmp);
 for(int i=1;i<=Tmax;i++){
     d[i]=d[i-1];
  Q=i;
  CautBin(1,N);
  //cout<<poz<<"\n";
  for(int j=poz;v[j].B==i;j++){
     d[i]=max(d[i],d[v[j].A]+(v[j].val));
     //cout<<"AHH\n";
    }
   rez=max(rez,d[i]);
  }
  fout<<rez;
 }