Slabě doleva vychýlené úseky posloupnosti
Je dána posloupnost P celých nezáporných čísel, v níž se žádná hodnota nevyskytuje vyskytuje více než jednou.P = a1, a2, ..., aN, kde N ≥ 2.
Úsek délky L posloupnosti P je každá podposloupnost ak, ak+1, ..., ak+L−1, kde 1 ≤ k; 2 ≤ L; k+L−1 ≤ N.
Úsek nazveme slabě doleva vychýlený, pokud index minimální hodnoty v tomto úseku je menší než index maximální hodnoty v tomto úseku, to jest minimální ze všech hodnot v úseku se nachází vlevo (ne nutně v bezprostředním sousedství) od maximální ze všech hodnot v tomto úseku.
Posloupnost P je dána takto:
a1 = S,
ai+1 = (754043 * ai + 500009) mod M, pro 1 ≤ i < N.
Hodnoty S, M jsou daná celá kladná čísla.
Úkolem je najít počet slabě doleva vychýlených úseků délky L v posloupnosti P.
Vstup
Na vstupu je jeden řádek se čtyřmi čísly představujícími postupně hodnoty N, L, S, M. Čísla jsou oddělena mezerou.Platí 2 ≤ N ≤ 1000000, 2 ≤ L ≤ N, 2 ≤ S ≤ 1000000, 2 ≤ M ≤ 2000000.
Výstup
Na výstupu je jediný řádek s jediným číslem představujícím počet slabě doleva vychýlených úseků délky L v dané posloupnosti.Poznámka
Je zřejmé, že díky dané maximální délce posloupnosti a délce zkoumaných úseků není účelné uvažovat o algoritmu s kvadratickou asymptotickou složitostí vzhledem k N nebo L.Příklad 1
Vstup:6 3 11 29Výstup:
3Posloupnost P je v tomto případě:
11 0 20 10 15 27
Příklad 2
Vstup:7 5 11 23Výstup:
0Posloupnost P je v tomto případě:
11 18 3 22 1 0 12
Příklad 3
Vstup:1000000 500000 519217 1000003Výstup:
270968
Veřejná data
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.