| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 2 | 1 | 1 | 100.000% |
Na poligon wojskowy w Bajtowie przywieziono n min lądowych, które ułożono w linii prostej. Każda mina jest położona w innym miejscu i ma swój promień rażenia. Po zdetonowaniu, mina automatycznie powoduje detonację tych wszystkich min w swoim zasięgu rażenia, które nie wybuchły jeszcze do tej pory. Mówimy, że mina a znajduje się w zasięgu rażenia miny b, jeśli odległość między nimi jest nie większa niż promień rażenia miny b.
Sierżant Bajtomir chce przeprowadzić eksperyment. Wybierze on dowolny podzbiór min (być może pusty) i rozkaże ręcznie zdetonować ten podzbiór min w tym samym momencie. Wynikiem eksperymentu jest zbiór min, które wybuchły – czy to w wyniku ręcznej detonacji, czy w wyniku wybuchu jakiejś innej miny.
Ile możliwych wyników eksperymentu może uzyskać Bajtomir? Dwa wyniki eksperymentu uznajemy za takie same, jeśli w ich wyniku wybuchły te same miny. Ponieważ wynik może być duży, wypisz jego resztę z dzielenia przez 109 + 7.
Pierwszy wiersz wejścia zawiera liczbę naturalną n (1 ≤ n ≤ 300 000) oznaczającą liczbę min. Każdy z kolejnych n wierszy zawiera po dwie liczby naturalne ai oraz ri (0 ≤ ai ≤ 1018, 0 ≤ ri ≤ 1018) oznaczające odpowiednio pozycję i-tej miny na prostej oraz jej promień rażenia. Możesz założyć, że a1 < a2 < a3 < . . . < an.
Podaj resztę z dzielenia przez 109 + 7 liczby różnych wyników eksperymentu, które może uzyskać Bajtomir po ręcznym zdetonowaniu wybranego przez siebie podzbioru min.
4 0 2 2 0 3 2 7 4
7
Wyjaśnienie przykładu: Można uzyskać 7 różnych wyników eksperymentu:
Zwróć uwagę na to, że ten sam wynik eksperymentu można często uzyskać na kilka różnych sposobów – na przykład wynik {1, 2} uzyskamy również, gdy zdetonujemy ręcznie miny 1 i 2.
Contest > Algorithmic Engagements > PA 2020 3-1번