시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1 | 1 | 1 | 100.000% |
Jarek dostał na gwiazdkę zestaw kostek domina o różnych wysokościach i ustawił je w rzędzie, stawiając każde na sztorc.
Jeśli Jarek przewróci w prawo domino o wysokości H ustawione na pozycji X, spowoduje to przewrócenie w prawo wszystkich kostek domina ustawionych na pozycjach X+1, X+2, ..., X+H. Analogicznie, jeśli Jarek przewróci w lewo domino o wysokości H ustawione na pozycji X, spowoduje to przewrócenie w lewo wszystkich kostek domina ustawionych na pozycjach X-1, X-2, ..., X-H. Kości przewrócone przez pierwszy element analogicznie przewracają kolejne.
Znając wysokość i pozycję każdej kostki domina oblicz maksymalną liczbę elementów które przewrócą się w wyniku przewrócenia jednej kostki w dowolną stronę.
W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ).
Pierwsza linia pojedynczego zestawu testowego zawiera liczbę naturalną N (1 <= N <= 105 ) oznaczającą liczbę kostek domina w zestawie. W kolejnych N liniach znajdują się po dwie liczby naturalne X i H (1<= X, H <= 109 ) oznaczające pozycję i wysokość kolejnych kostek domina. Pozycje kostek są podane w kolejności rosnącej.
Dla każdego zestawu testowego należy w osobnej linii wypisać maksymalną liczbę kostek domina jaka może zostać przewrócona w wyniku przewrócenia jednego elementu.
1 4 1 2 4 1 5 2 7 1
3
Contest > Spot > CoolSpot 2011 3-2번