Pagini recente » Cod sursa (job #2965612) | Cod sursa (job #2611098) | Cod sursa (job #553977) | Cod sursa (job #657973) | Cod sursa (job #712124)
Cod sursa(job #712124)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100001
using namespace std;
struct Interval
{
Interval() :
st(0),
end(0)
{}
Interval(const int s, const int e) :
st(s),
end(e)
{}
inline bool operator < (const Interval& i) const
{
if (end < i.end)
{
return true;
}
else if (end == i.end)
{
return st > i.st;
}
return false;
}
int st, end;
};
unsigned int AirTimes[MAXN];
unsigned int Gains[MAXN];
int FindLastBand(const vector<Interval>& vBands, const int size, const int start)
{
int step = 1;
while (step <= size)
{
step <<= 1;
}
int i=0;
for (;step>0; step>>=1)
{
if (i+step<=size && vBands[size - i - step].end > start)
{
i += step;
}
}
return size-i-1;
}
int main()
{
int n;
vector<Interval> vBands;
fstream fin("heavymetal.in", fstream::in);
fstream fout("heavymetal.out", fstream::out);
fin >> n;
//cout << n << "\n";
for (int i=0; i<n; ++i)
{
int st, end;
fin >> st >> end;
vBands.push_back(Interval(st,end));
}
sort(vBands.begin(), vBands.end());
for (int i=0; i<n; ++i)
{
Gains[i] = AirTimes[i] = vBands[i].end - vBands[i].st;
//cout << vBands[i].st << " " << vBands[i].end << " " << AirTimes[i] << "\n";
}
/*int index = FindLastBand(vBands, vBands.size(), 2);
cout << index << "\n";
cout << vBands[index].st << " " << vBands[index].end << endl << endl;*/
unsigned int maxTime = 0;
for (int i=0; i<vBands.size(); ++i)
{
int index = FindLastBand(vBands, i, vBands[i].st);
if (index >=0)
{
const int ending = vBands[index].end;
//cout << index << endl;
while (index >=0)
{
Gains[index] = max(Gains[index], AirTimes[index]+Gains[i]);
maxTime = max(maxTime, Gains[index]);
index--;
}
}
}
/*for (int i=0; i<n; ++i)
{
cout << Gains[i] << " ";
}
cout << "\n";*/
fout << maxTime << "\n";
fin.close();
fout.close();
return 0;
}