Cod sursa(job #2533909)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 29 ianuarie 2020 20:37:34
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 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)//le ordonam crescator dupa timpul de final
{
    if(a[i].y>a[j].y)return 1;
    if(a[i].y==a[j].y&&a[i].x>a[j].x)return 1;//crescator dupa timpul de inceput
    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()
{
    //cautare binara
    //in lg[i]-timpul maxim de concert pana la spectacolul i
    //vedem daca e mai bina sa folosim/nu spectacolul
    //raspunsul va fi in lg[N]
    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];//pp ca nu il folosim
        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)//daca se sfarseste inaintea inceperii spectacolului curent
            {
                poz=max(m,poz);//retinem pozitia,mereu vom gasi una mai buna
                st=m+1;
            }
            else dr=m-1;
        }
        lg[i]=max(lg[i],lg[poz]+durata);//vedem daca e mai convenabil sa il folosim
    }
    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);
    //bubblesort();
   // print();
    solve();


    return 0;
}