Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP7_1H - Plot |
Dom sołtysa pewnej wsi otacza płot złożony z n sztachet ponumerowanych od 0 do n-1. Płot ten od lat nie był malowany i wygląda naprawdę obskurnie. Nasz gospodarz postanowił to zmienić. Zamierza on poprosić mieszkańców wsi, aby każdy z nich pomalował dowolnie wybrany fragment płotu. Zanim jednak to uczyni potrzebny jest mu system informatyczny umożliwiający wykonywanie dwóch rodzajów operacji:
- 0 a b - oznaczenie fragmentu płotu od sztachety a-tej do b-tej jako pomalowanego.
- 1 a b - obliczenie ile sztachet w przedziale od a-tej do b-tej jest pomalowanych.
Twoim zadaniem jest stworzenie tego systemu.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [1;200000] i m ∈ [1;200000] oznaczające odpowiednio: liczbę sztachet wchodzących w skład ogrodzenia oraz liczbę operacji do wykonania. W kolejnych m liniach znajdują się polecenia.
Każda operacja składa się z trzech liczb: t ∈ [0;1], a ∈ [0;n-1] i b ∈ [a;n-1] oznaczających odpowiednio typ operacji oraz granice przedziału, na którym operujemy.
Wyjście
Dla każdego polecenia typu 1 należy, w osobnej linii wypisać, liczbę pomalowanych sztachet w przedziale [a;b].
Przykład
Wejście
10 5 0 2 4 0 8 9 1 3 8 0 7 7 1 0 7
Wyjście
3 4
Dodane przez: | Maciej Boniecki |
Data dodania: | 2015-03-21 |
Limit czasu wykonania programu: | 0.5s-1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 JS-MONKEY SCM qobi |
Pochodzenie: | VII Mistrzostwa WWSI w Programowaniu |