Pagini recente » Cod sursa (job #251365) | Cod sursa (job #3254816) | Cod sursa (job #524046) | Cod sursa (job #954455) | Cod sursa (job #595346)
Cod sursa(job #595346)
#include<fstream>
# define maxn 100005
using namespace std;
typedef struct { long st,dr; } interval;
interval T[maxn];
long REZ[maxn];
long i,j,n;
long maxim,poz,maxim2;
long BS ( int val ) {
int i, cnt ;
for (cnt = 1; cnt << 1 <= n; cnt <<= 1) ;
for (i = 0; cnt; cnt >>= 1)
if (i + cnt <= n && T[i + cnt].st < val)
i += cnt ;
return i ;
}
bool mysort ( interval a, interval b)
{
if ( a.st > b.st )
return 0;
if ( a.st < b.dr )
return 1;
if ( a.dr < b.dr )
return 0;
return 1;
}
int main()
{
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
in>>n;
for ( i=1; i<=n; ++i )
in>>T[i].st>>T[i].dr;
sort(T+1,T+n+1,mysort);
for ( i=1; i<=n; ++i )
{
if ( REZ[i]>maxim)
maxim=REZ[i];
if ( maxim+T[i].dr-T[i].st > maxim2)
maxim2=maxim+T[i].dr-T[i].st;
poz=BS(T[i].dr);
poz++;
REZ[poz]=max(REZ[poz],maxim+T[i].dr-T[i].st);
}
out<<maxim2<<"\n";
return 0;
}