Aţi auzit despre Nessie? Este un pleziozaur misterios care trăieşte în adâncurile lacului Loch Ness din munţii Scoţiei. Cu mulţi ani în urmă el a fost zărit pentru prima oară la suprafaţa lacului, iar de atunci, spre desfătarea turiştilor, el îşi face apariţia în mod periodic.
Nessie ştie de la managerii Loch Ness care este programul de vizitare a lacului pentru un interval de N zile. Mai exact, el cunoaşte datele primei și ultimei zile de şedere în preajma lacului pentru fiecare turist.
Contractul pe care Nessie l-a semnat cu managerii prevede faptul că fiecare dintre turişti trebuie să aibă posibilitatea să-l zărească, însă doar de departe şi doar o singură dată, deoarece Nessie intenţionează să rămână în continuare misterios. Pot exista zile fără turişti şi în aceste zile Nessie profită de fiecare dată ca să iasă la suprafaţa lacului.
Cerinţă
Cunoscând prima şi ultima zi de şedere pentru fiecare turist, şi numărul total de zile prevăzute în contract, determinaţi numărul maxim de ieşiri la suprafaţa lacului, pe care Nessie le poate face, astfel încât fiecare turist să-l zărească o singură dată.
Date de intrare
Fișierul de intrare nessie.in conține pe prima linie numerele naturale N și T, separate printr-un spațiu, unde N este numărul de zile prevăzute în contract iar T este numărul de turişti. Pe următoarele T linii se află câte două valori naturale separate prin câte un spațiu. Numerele a[i] şi b[i] de pe linia i+1 reprezintă prima, respectiv ultima zi de şedere în preajma lacului Loch Ness pentru turistul i.
Date de ieșire
Fișierul de ieșire nessie.out va conține pe prima linie un număr natural care reprezintă numărul maxim de apariţii ale lui Nessie pe suprafaţa lacului, astfel încât fiecare turist să-l zărească o singură dată.
Restricții și precizări
2 ≤ N, T ≤ 250 0001 ≤ a[i] ≤ b[i] ≤ N2 * Pot exista mai mulți turiști care vizitează lacul în aceeași perioadă * În cazul în care nu există soluţie se va afişaIMPOSIBIL@- Nessie iese la suprafaţa lacului cel mult odată pe zi
Exemplul 1
nessie.in
5 2 1 3 4 5
nessie.out
2
Explicație
Nessie poate ieşi la suprafaţă o dată în una din zilele 1, 2 sau 3 pentru primul turist şi încă odată în ziua 4 sau în ziua 5 pentru al doilea turist.
Exemplul 2
nessie.in
7 3 2 5 3 4 6 7
nessie.out
3
Explicație
Nessie poate ieşi în ziua 1, când nu sunt turişti, mai poate ieşi odată în ziua 3 sau ziua 4 pentru primul şi al doilea turist şi a treia oară în ziua 6 sau ziua 7 pentru al treilea turist.
Exemplul 3
nessie.in
7 3 3 5 1 4 6 7
nessie.out
3
Explicație
Nessie poate ieşi în ziua 1 pentru al doilea turist, în ziua 5 pentru primul turist și în ziua 6 sau 7 pentru al treilea turist.
Exemplul 4
nessie.in
6 3 1 6 2 3 4 5
nessie.out
IMPOSIBIL
Explicație
Nessie nu poate ieși la suprafață atât pentru turistul 2 cât și pentru turistul 3 fără să fie zărit de două ori de către primul turist.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Nessie:
/*
prof. Constantin Galatan
O(n)
*/
#include <cstdio>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
using VI = vector<int>;
const int Inf = 0x3f3f3f3f;
void get(int &x);
VI a, Min, Max;
int T, n;
int main()
{
freopen("nessie.in", "r", stdin);
freopen("nessie.out", "w", stdout);
get(n); get(T);
a = Max = VI(n + 1);
Min = VI(n + 2, n + 1);
int x, y;
while ( T-- )
{
get(x); get(y);
Min[y] = min(Min[y], x);
Max[y + 1] = max(Max[y + 1], x);
}
for (int i = n; i >= 0; i--)
Min[i] = min(Min[i], Min[i + 1]);
for (int i = 1; i <= n; i++)
Max[i] = max(Max[i], Max[i - 1]);
int i0(1);
deque<int> q;
for (int i = 1, imax, imin; i <= n; i++)
{
imin = max(Max[i], 1); imax = min(i - 1, Min[i] - 1);
if ( imin > imax ) {
a[i] = -Inf;
continue;
}
for (; i0 <= imax; q.push_back(i0++) )
while ( !q.empty() && a[q.back()] <= a[i0] )
q.pop_back();
while (!q.empty() && imin > q.front())
q.pop_front();
if ( !q.empty() )
a[i] = max(a[q.front()], 0) + 1;
}
if ( a[n] < 0 )
printf("IMPOSIBIL\n");
else
printf("%d\n", a[n] + 1);
return 0;
}
const int Lim = 100000;
int p = Lim - 1;
char s[Lim];
void Next()
{
if (++p == Lim)
fread(s, 1, Lim, stdin), p = 0;
}
void get(int &x)
{
for (; s[p] < '0' || s[p] > '9'; Next());
for (x = 0; s[p] >= '0' && s[p] <= '9'; Next())
x = x * 10 + s[p] - '0';
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1235 Nessie
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1235 Nessie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!