Cod sursa(job #2778173)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 29 septembrie 2021 19:04:01
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

//4
//3 5
//5 10
//3 4
//1 2

const int maxN = (int)1e5;

int n;

int maxLen[maxN + 5];

pair<int, int> segments[maxN + 5];

bool rev(const pair<int, int> &st, const pair<int, int> &snd) {
  return st.second < snd.second;
}

int main() {
  in >> n;
  for (int i = 1; i <= n; i++) {
    in >> segments[i].first >> segments[i].second;
  }
  sort(segments + 1, segments + n + 1, rev);
  maxLen[1] = segments[1].second - segments[1].first;
  for (int i = 2; i <= n; i++) {
    maxLen[i] = maxLen[i - 1];
    if (segments[i].first >= segments[i - 1].second) {
      maxLen[i] = maxLen[i - 1] + segments[i].second - segments[i].first;
    } else {
      int l = 1, r = i - 2, pos = 0;
      while (l <= r) {
        int m = (l + r) / 2;
        if (segments[m].second <= segments[i].first) {
          pos = m;
          l = m + 1;
        } else {
          r = m - 1;
        }
      }
      maxLen[i] = max(maxLen[i], maxLen[pos] + segments[i].second - segments[i].first);
    }
  }
  out << maxLen[n] << "\n";
  return 0;
}