Probabil că ar trebui îmbunătățite testele. Am luat 100 cu sursa care nu verifica cazul în care segmentele ce se intersectau erau coliniare.

Am exact aceeasi problema, cum s-a postat mai sus. Am testat pe niste teste mai mari si formatul de output corespunde la cel descris in enunt...

Un hint cine a trecut de testul 16...?

Am o intrebare, pentru numarul de chei magice pe testul de pe pagina problemei de ce raspunsul e 2?
Oare nu sunt bune si asa variante ale matricei cum sunt:
9 1 1
1 9 1
9 9 1
sau
1 1 1
9 9 1
9 1 9
?
L.E. Nevermind , nu citisem atent conditia ca sa fie crescatoare permutarile. In fine, am rezolvat-o.

Imi poate spune cineva cat va da cu o sursa de 100p pe urmatorul test:
23
9 20
21 25
7 11
9 27
25 27
6 10
18 28
15 21
9 25
8 14
8 25
2 9
23 28
1 10
4 24
11 23
8 16
13 24
3 26
8 17
9 18
2 12
5 20
25
18
3
19
3
16
18
25
6
16
15
20
17
6
9
4
9
2
24
6
25
11
11

Multumesc Anticipat.

[L.E] Am luat suta.
raspuns (sper ca ajuta cuiva):
12 18
14 3
22 5
15 16
6 14
23 20
19 9
3 17
10 15
17 22
20 23
21 11
1 10
8 6
16 13
18 7
11 2
9 4
4 12
2 19
5 21
7 8
13 1

Imi poate spune cineva , cat va da pentru urmatorul test:
50
2 1
4 1
72 -1
42 -1
1 1
4 1
52 -1
4 -1
4 1
5 -1
1 -1
52 -1
4 1
5 -1
5 1
81 1
94 1
94 -1
42 -1
4 -1
4 1
5 1
8 1
82 -1
42 -1
4 1
4 1
4 -1
5 1
21 1
15 -1
21 -1
25 1
52 1
52 -1
58 1
42 1
52 1
52 -1
84 1
78 -1
42 -1
5 -1
42 1
1 -1
5 1
2 1
1 1
1 -1
4 -1

Multumesc Anticipat.

Multumesc mult pentru explicatie, chiar e frumoasa problema. E mai usor decat credeam. 

Imi poate da cineva un hint ,cam cum ar arata dinamica pe arbore ? nu prea am facut probleme de asa gen..

arborele este binar ? sau un nod poate avea mai mult de 2 descendenti ?
L.E. Intradevar arborele nu este binar. Se intelege si din explicatia la testul de pe site, nu am observat deodata, my bad =\
Iata si un test , poate ii va fi de ajutor cuiva :
15 1
1 1 2 2 3 4 4 6 6 7 7 9 10 13
Out: 4
Daca modificati K , atunci pentru urmatoarele valori ale lui k aveti urmatorul raspuns:
k=1,2 out=4 , k=3,4 out=3, k=5,6 out=2 , k=12 out=1.

Ma uit ca multe surse au memorie consumata sub 300 Kb . E o abordare greedy sau e dinamica doar cu vectori ?

Intuieste cineva ce are testul 8 ? Solutia mea e asemanatoare cu cea descrisa de usurelu catalin .

Cat va da pentru testul respectiv?
1 2
-5 -5

numarul de pixeli a unei cifre este fixa pentru fiecare test ? si in programul de generare a testelor atasat la problema genereaza teste in care numarul pixelor difera cu testul de pe site...

Folosesc sortarea din stl ,dar am facut functia de comparare aparte, si am si verificat sortarea pe asha cazuri . Poate cineva care a facut cu arbori de intervale sa-mi explice poate cumva altfel ar trebui sa lucrez cu arborele...

L.E. S-a rezolvat. Era problema cu functia de comparare a sortare , in ciuda faptului ca credeam ca merge perfect sortarea.

Am facut o rezolvare dupa cum e spus in solutia oficiala dar iau doar 70p. Mă gândesc că greseala ar putea fi in cautarea numarului de pozitii mai mari ca cea curenta.
Eu fac asa:partea cu sortarea , apoi caut in arbore pozitia curenta+1 si cind o gasesc ca limita de jos a intervalului ce-l contine nodul dat atunci adaug valoarea data si adaug si valoarea descendentului drept in caz ca div+1>val , apoi introduc in arbore si pozitia elementului curent. Poate are cineva idei unde ar putea fi greseala ?

Imi poate recomanda cineva vri-un articol care m-ar ajuta sa rezolv problema data ?

Imi poate sugera cineva de ce imi pica al 2-lea test...in rest toate merg perfect, am 95 puncte si nu-mi pot gasi greseala in program...