Cod sursa(job #1972150)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 22 aprilie 2017 10:38:22
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAX_N = 100000;

struct Interval {
  int x;
  int y;
  
  bool operator <(const Interval &other) const {
    return this->y < other.y || (this->y == other.y && this->x < other.x);
  }
};

Interval v[5 + MAX_N];
int d[5 + MAX_N];

int main() {
  freopen ("heavymetal.in", "r", stdin);
  freopen ("heavymetal.out", "w", stdout);
  
  int n, st, dr, med, val, myMax;
  scanf ( "%d", &n );
  for (int i = 1; i <= n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    v[i].x = x;
    v[i].y = y;
  }
  sort (v + 1, v + n + 1);
  myMax = 0;
  for (int i = 1; i <= n; ++i) {
    st = 1;
    dr = i;
    val = v[i].x;
    while (st < dr) {
      med = (st + dr) / 2;
      if (v[med].y <= val)
        st = med + 1;
      else
        dr = med;
    }
    med = (st + dr) / 2;
    if (v[med].y > val)
      med--;
    d[i] = max (d[med]+v[i].y-v[i].x, myMax);
    if (d[i] > myMax)
      myMax = d[i];
  }
  printf ("%d", myMax);
  return 0;
}