Cod sursa(job #2553854)

Utilizator mihaiailincai1Mihai Ailincai mihaiailincai1 Data 22 februarie 2020 12:30:07
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>

#include<fstream>

#include<algorithm>

#define N 100005

using namespace std;

ifstream fin("heavymetal.in");

ofstream fout("heavymetal.out");



struct pereche

{

    int x,y;

};



pereche a[N];

int lg[N];

int n;



int compara(int i,int j)
{

    if(a[i].y>a[j].y)return 1;

    if(a[i].y==a[j].y&&a[i].x>a[j].x)return 1;
    return 0;

}



int pivotare(int s,int d)

{

    int pasi=0,pasj=1,i=s,j=d;

    int p=s+rand()%(d-s+1);

    pereche aux=a[s];a[s]=a[p];a[p]=aux;



    while(i<j)

    {

        if(compara(i,j)==1)

        {

            aux=a[i];a[i]=a[j];a[j]=aux;

            pasi=1-pasi;

            pasj=1-pasj;

        }

        i+=pasi;

        j-=pasj;

    }

    return i;

}



void qs(int s,int d)

{

    if(s<d)

    {

        int p=pivotare(s,d);

        qs(s,p-1);

        qs(p+1,d);

    }

}



void bubblesort()

{

    int i;

    pereche aux;

    bool ordo=false;

    while(ordo=false)

    {

    ordo=true;

    for(i=1;i<n;++i)

        if(compara(i,i+1)==1)

    {

        ordo=false;

        aux=a[i];a[i]=a[i+1];a[i+1]=aux;

    }

    }

}





void solve()

{



    int i,m,poz,st,dr,durata;

    lg[1]=a[1].y-a[1].x;

    for(i=2;i<=n;++i)

    {

        lg[i]=lg[i-1];

        durata=a[i].y-a[i].x;

        st=1,dr=i;poz=0;

        while(st<=dr)

        {

            m=(st+dr)/2;

            if(a[m].y<=a[i].x)

            {

                poz=m;

                st=m+1;

            }

            else dr=m-1;

        }

        lg[i]=max(lg[i],lg[poz]+durata);
    }

    fout<<lg[n];

}



void print()

{

    int i;

    for(i=1;i<=n;++i)



        fout<<a[i].x<<" "<<a[i].y<<"\n";

}



int main()



{

    int i;

    fin>>n;

    for(i=1;i<=n;++i)

        fin>>a[i].x>>a[i].y;

    qs(1,n);


    solve();





    return 0;

}