Contest problemset description

Jasio zainteresował się hodowlą truskawek. Rodzice przeznaczyli mu do dyspozycji jedno poletko ich ogrodu. Można myśleć, że jest to prosty, długi odcinek ogrodu, wzdłuż którego Jasio może hodować swoje truskawki. Z oczywistych powodów rządek należy pokryć agrowłókniną. Jasio ma do dyspozycji N kawałków materiału. Ustalił już, że i-ty kawałek powinien położyć od l_i-tego do r_i-tego metra poletka. Ze względu na duże wiatry w rodzimych stronach Jasia, tkaninę należy odpowiednio zabezpieczyć przed porwaniem przez podmuchy wiatru. Ustalił, że i-ty kawałek powinien zostać przymocowany do gleby przy pomocy co najmniej w_i specjalnych szpilek, aby mieć pewność, że siły natury nie zniszczą jego uprawy. Szpilkę można wbić w dowolny odcinek tkaniny, łącznie z krawędziami. Jako, że agrowłóknina jest bardzo cienka, to nie ma żadnego problemu, żeby jedna szpilka została przełożona przez wiele warstw tkaniny jednocześnie.

Jasio chciałby kupić jak najmniej szpilek, ale sam spędza całe dnie nad pielęgnowaniem i doglądaniem swojej plantacji. Pomóż mu i napisz program ile co najmniej szpilek musi kupić, żeby zrealizować swój plan pokrycia grządki agrowłókniną.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę kawałków agrowłókniny. W kolejnych N wierszach następuje opis kawałków. W i + 1-wszym wierszu znajdują się trzy liczby naturalne oddzielone pojedynczymi spacjami l_i, r_i oraz w_i, oznaczające odpowiednio lewy koniec włókniny, prawy koniec włókniny oraz liczbę szpilek, którą należy wbić w ten odcinek tkaniny.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba naturalna, oznaczająca minimalną liczbę potrzebnych szpilek.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ l_i < r_i ≤ 10⁹, 1 ≤ w_i ≤ 10⁹.

W testach wartych 20% punktacji zachodzi warunek N ≤ 10.

W testach wartych 30% punktacji zachodzi warunek r_i ≤ 500 000.

Przykład

4
1 5 6
2 3 4
5 7 7
1 7 10

11

Wiktor walczy z zadaniem Zamek z XXIV Olimpiady Informatycznej. Zadanie ma już prawie rozwiązane, ale niestety, nie działa na niektórych przygotowanych przez niego testach. Wiktor mógłby łatwiej zdebugować program, gdyby przygotowane przez niego testy mógł wyświetlić w terminalu.

Mapa zamku naniesiona jest na układ współrzędnych i mieści się w całości w prostokącie, którego lewy dolny róg znajduje się w punkcie (0,0), a prawy górny róg w (w,h). Zamek dzieli się na komnaty, które w całości wypełniają zamek. Jedna z komnat jest komnatą początkową, a jedna końcową. Niektóre z komnat mogą być zablokowane. Napisz kod, który wczyta opis zamku i narysuje go jako ASCII-art na ekranie!

Wejście

W pierwszym wierszu standardowego wejścia znajdują się cztery liczby naturalne w, h, N i M, oznaczające odpowiednio wymiar mapy, liczbę komnat zamku oraz liczbę blokad. W drugim wierszu znajduje się para liczb x_p, y_p oznaczające współrzędne punktu początkowego. W trzecim wierszu znajdują się liczby x_s, y_s oznaczające współrzędne punktu końcowego. Obie pary współrzędnych znajdują się wewnątrz pewnej komnaty (a nie na brzegu).

W następnych N wierszach znajdują się opisy komnat, i-ty z nich zawiera cztery liczby całkowite x₁, y₁, x₂, y₂ oznaczające, że prostokąt odpowiadający i-tej komnacie ma przeciwległe wierzchołki w punktach (x₁,y₁) oraz (x₂,y₂).

W następnych M wierszach znajdują się opisy blokad. i-ty z nich składa się z dwóch liczb całkowitych x, y oznaczających, że komnata zawierająca punkt (x,y) jest zablokowana.

Wyjście

Na wyjściu należy narysować ASCII-art odpowiadający mapie zamku. Ze względu na to, że wszystkie znaki mają tę samą szerokość i wysokość, należy myśleć, że osie pionowe i poziome układu współrzędnych (tj. wszystkie proste pionowe i poziomie przechodzące przez punkty kratowe) mają tę samą szerokość i wysokość, co kwadraty 1 × 1 pomiędzy nimi. Zatem pierwsze pole pierwszego wiersza wyjścia reprezentuje punkt (0,h), a pole o rogach w (0,h) oraz (1,h−1) reprezentuje drugi znak drugiego wiersza. Rogi wszystkich komnat powinny zostać oznaczone znakiem +. Pionowe ściany komnat powinny zostać narysowane przy użyciu znaków |, poziomie przy pomocy -. Punkt początkowy powinien zostać oznaczony przy pomocy pojedynczego znaku P. Punkt końcowy powinien zostać oznaczony przy pomocy pojedynczego znaku S. Zablokowane komnaty powinny zostać w całości wypełnione znakami X. W innym razie powinny być wypełnione znakami spacji. Dla rozjaśnienia zalecane jest zapoznanie się z testem przykładowym.

Ograniczenia

1 ≤ w, h ≤ 2000, 1 ≤ N, M ≤ 1 000 000, wszystkie współrzędne x, y spełniają nierówności 0 ≤ x ≤ w, 0 ≤ y ≤ h.

W testach wartych 50% punktacji zachodzi dodatkowy warunek M = 0 (tzn. nie występują żadne blokady).

Przykład

7 6 9 3
1 1
6 4
0 0 3 2
3 1 6 3
3 0 5 1
5 0 7 1
6 1 7 3
0 2 3 6
3 3 5 5
3 5 5 6
5 3 7 6
4 2
5 2
4 4

+-----+---+---+
|     |   |   |
|     +---+   |
|     |XXX|   |
|     |XXX| S |
|     |XXX|   |
|     +---+-+-+
|     |XXXXX| |
+-----+XXXXX| |
|     |XXXXX| |
| P   +---+-+-+
|     |   |   |
+-----+---+---+

5 5 4 0
1 1
4 4
0 0 3 3
0 3 3 5
3 0 5 2
3 2 5 5

+-----+---+
|     |   |
|     | S |
|     |   |
+-----+   |
|     |   |
|     +---+
|     |   |
| P   |   |
|     |   |
+-----+---+

Jasio zarządza lokalnym sklepem. W sklepie jest N regałów ustawionych jeden obok drugiego. Na każdym regale leżą przedmioty jednego rodzaju, który oferuje sklep Jasia. Rodzaje przedmiotów ponumerowane są liczbami naturalnymi od 1 do N. Jasio co jakiś czas decyduje, żeby zmienić typ przedmiotów na niektórych regałach. Musi również co jakiś czas przeprowadzać inwentaryzację. Pojedyncza inwentaryzacja polega na sprawdzeniu liczby regałów w przedziale od l-tego do r-tego, które mają wystawione przedmioty o ustalonym rodzaju v. Jasio poprosił Cię o napisanie systemu, który pozwoli mu przyspieszyć proces inwentaryzacji.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q, oznaczające odpowiednio liczbę regałów oraz liczbę zapytań Jasia. W drugim wierszu wejścia znajduje się N liczb naturalnych p₁, …, p_N oznaczające początkowe rodzaje przedmiotów na kolejnych regałach sklepu Jasia. W następnych Q wierszach następuje opis zapytań. i-ty opis rozpoczyna się od jednego znaku t_i. Jeżeli t_i = Z, to w tym samym wierszu następują dwie liczby naturalne z_i, v_i oznaczające, że Jasio zmienił rodzaj przedmiotów na z_i-tym regale na v_i. Jeżeli t_i = I, to w tym samym wierszu następują trzy liczby naturalne v_i, l_i, r_i oznaczające, że Jasio chce przeprowadzić inwentaryzację regałów od l_i-tego do r_i-tego włącznie dla przedmiotów o rodzaju v_i.

Wyjście

Dla każdego zapytania typu I należy wypisać jedną liczbę naturalną odpowiadającą na dane pytanie Jasia.

Ograniczenia

1 ≤ N, Q ≤ 500 000, 1 ≤ v_i, p_i, z_i ≤ N, 1 ≤ l_i ≤ r_i ≤ N.

W testach wartych łącznie 20% punktów zachodzi dodatkowy warunek N, Q ≤ 2000.

W testach wartych łącznie 40% punktów zachodzi dodatkowy warunek t_i = I dla każdego i.

Przykład

3 4
1 2 3 
I 1 1 3
Z 2 1
I 1 1 2
I 2 2 3

1
2
0