Pagini recente » Cod sursa (job #2605140) | Cod sursa (job #1324434) | Cod sursa (job #524274) | Cod sursa (job #838407) | Cod sursa (job #2533909)
#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;
}