# PBinfo #4054 – segmax – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Vom considera un segment pe axa Ox care începe la poziția 0 și se termină la poziția L.
Se vor insera pe rând N puncte pe axă, iar după fiecare punct inserat se va afișa lungimea celui mai lung segment delimitat de două puncte (inclusiv 0 și L).

Date de intrare
Programul citește de la tastatură numerele L și N, iar apoi N numere naturlae, reprezentând punctele care urmează să fie inserate.

Date de ieșire
Programul va afișa pe ecran N linii, a i-a linie reprezentând lungimea celui mai lung segment delimitat de două puncte, după inserarea celui de al i-lea punct.

Restricții și precizări

1 ≤ N ≤ 100 000
1 ≤ L ≤ \({10}^{18}\)
Fiecare punct inserat se află în intervalul (0, L)
Punctele inserate sunt distincte.
Punctele 0 și L se consideră inserate de la început.
În cadrul acestei probleme, vom defini lungimea unui segment ca fiind numărul de puncte cu coordonate numere naturale care se află pe segmentul dat.

Exemplu:
Intrare

20 4
6
11
15
4
Ieșire

15
10
7
6
Explicație:
Segmentele de lungimi maxime sunt [6, 20], [11, 20], [0, 6], respectiv [15, 20].

## Cod sursă C++

```cpp
// Soluție Bogdan Vlad-Mihai, clasa a XII-a, Liceul Teoretic "Aurel Vlaicu" Orăștie
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll l; cin >> l;
  int n; cin >> n;
  vector<ll> v(n);
  for (ll &x : v)
    cin >> x;
  multiset<ll> lengths;
  set<ll> points;
  lengths.insert(-(l + 1));
  points.insert((ll)0);
  points.insert(l);
  for (ll x : v) {
    auto lowerLimit = points.lower_bound(x);
    lowerLimit--;
    auto low = *lowerLimit, up = *points.upper_bound(x);
    lengths.erase(lengths.find(-(up - low + 1)));
    lengths.insert(-(up - x + 1));
    lengths.insert(-(x - low + 1));
    points.insert(x);
    cout << -(*lengths.begin()) << "\n";
  }
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4054)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4054/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4054/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)