Cod sursa(job #2534039)

Utilizator amalia.gemanGeman Aamalia amalia.geman Data 29 ianuarie 2020 23:26:19
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#define N 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct concert
{
    int x; ///inceput
    int y; ///final
} a[N];
int n;


void Read()
{
    int i;
    fin >> n;
    for(i=1; i<=n; i++)
        fin >> a[i].x >> a[i].y;
}

int Pivotare(int s, int d)
{
    int i=s, j=d, pasi=0, pasj=1;
    while(i < j)
    {
        if(a[i].y < a[j].y)
        {
            swap(a[i].x,a[j].x);
            swap(a[i].y,a[j].y);
            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 Solve()
{
    int i, ant;
    long long s;

    ant=a[1].x;
    s=a[1].y-a[1].x;

    for(i=2; i<=n; i++)
        if(a[i].y<=ant)
        {
            s+=(a[i].y-a[i].x);
            ant=a[i].x;
        }
    fout<<s;
}

int main()
{
    Read();
    QS(1,n);
    Solve();///sortare crescatoare dupa timpul final
    return 0;
}