Pagini recente » Cod sursa (job #1438096) | Cod sursa (job #865736) | Cod sursa (job #376572) | Cod sursa (job #673517) | Cod sursa (job #1851475)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
void Normalizeaza(vector<int> &v)
{
sort(v.begin(), v.end());
vector<int> unic;
for (unsigned i = 0; i < v.size(); ++i) {
if (i == 0 || v[i] != v[i - 1]) {
unic.push_back(v[i]);
}
}
v = unic;
}
int Rang(const vector<int> &v, int x)
{
int st = 0, dr = v.size() - 1;
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (v[mij] == x) {
return mij + 1;
} else if (v[mij] > x) {
dr = mij - 1;
} else {
st = mij + 1;
}
}
return -1;
}
int PutereZerouri(int x)
{
return (x ^ (x - 1)) & x;
}
int GasesteMax(const vector<int> &aib, unsigned poz)
{
int rez = 0;
while (poz > 0) {
rez = max(rez, aib[poz]);
poz -= PutereZerouri(poz);
}
return rez;
}
void Actualizeaza(vector<int> &aib, unsigned poz, int val)
{
while (poz < aib.size()) {
aib[poz] = max(aib[poz], val);
poz += PutereZerouri(poz);
}
}
int main()
{
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n;
fin >> n;
vector<int> ranguri;
vector<pair<int, int>> intervale(n);
for (int i = 0; i < n; ++i) {
int x, y;
fin >> x >> y;
intervale[i] = {x, y};
ranguri.push_back(x);
ranguri.push_back(y);
}
Normalizeaza(ranguri);
auto cmpInter = [] (const pair<int, int> &a, const pair<int, int> &b) -> bool
{
return a.second < b.second;
};
sort(intervale.begin(), intervale.end(), cmpInter);
vector<int> aib(ranguri.size() + 1);
int rez = 0;
for (const auto &inter : intervale) {
int rang_x = Rang(ranguri, inter.first);
int rang_y = Rang(ranguri, inter.second);
int len = inter.second - inter.first;
int len_total = GasesteMax(aib, rang_x) + len;
rez = max(rez, len_total);
Actualizeaza(aib, rang_y, len_total);
}
fout << rez << "\n";
return 0;
}