Cod sursa(job #2051882)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 29 octombrie 2017 17:48:20
Problema Heavy metal Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");
typedef struct time{int x,y,dif;} TIME;
TIME A[100001];
int n,i,j,ind,B[100001];
long long Best[100001];

bool cmp(TIME a, TIME b)
{
    return a.y<b.y;
}

int bs(int st, int dr, int val)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(B[mij]<val)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st;
}

void normalizare()
{
    sort(B+1,B+2*n+1);
    for(i=1; i<=n; i++)
    {
        A[i].x=bs(1,2*n,A[i].x);
        A[i].y=bs(1,2*n,A[i].y);
    }
}

int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
    {
        fi>>A[i].x>>A[i].y;
        A[i].dif=A[i].y-A[i].x;
        B[2*i-1]=A[i].x;
        B[2*i]=A[i].y;
    }
    normalizare();
    sort(A+1,A+n+1,cmp);
    ind=1;
    for(i=1; i<=A[n].y; i++)
    {
        Best[i]=Best[i-1];
        while(ind<=n && A[ind].y<=i)
        {
            if(A[ind].y==i)
                Best[i]=max(Best[i],Best[A[ind].x]+A[ind].dif);
            ind++;
        }
    }
    fo<<Best[A[n].y]<<"\n";
    fi.close();
    fo.close();
    return 0;
}