스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
I PO-juryns 100% originella spel String Instrument Champion visas noter i en låt som punkter på en gitarrs strängar. Noterna representeras som heltal, där heltalet representerar tonhöjden hos noten. Inga två noter spelas samtidigt i någon av String Instrument Champion's låtar.
En låt kan innehålla många fler noter än det finns strängar på gitarren. Därför placerar vi ut noterna på stängarna enligt en viss uppsättning regler. Det går bra ibland, men inte alltid. När vi placerar ut noterna på strängarna har vi följande krav:
- Den första noten får vara på valfri sträng.
- Om den senaste noten hade lägre tonhöjd än nästa not, så måste nästa not vara på en högre sträng.
- Om den senaste noten hade högre tonhöjd än nästa not, så måste nästa not vara på en lägre sträng.
- Om den senaste noten hade samma tonhöjd som nästa not, så måste nästa not vara på samma sträng.
Du får en låt med n 1-indexerade toner, och gitarren har m strängar. Du får också q intervall i låten. Ett intervall representeras av heltalen a och b, där första noten i intervallet har index a och sista noten index b.
För varje intervall undrar vi nu: är det möjligt att placera ut de noter som är med i intervallet på strängar så att kraven är uppfyllda?
Indata
Den första raden innehåller tre heltal n, m och q (1 ≤ n, m, q ≤ 10^5). Den andra raden innehåller n heltal t_i (1 ≤ t_i ≤ 10^9). Sen följer q rader med två heltal a_i och b_i vardera (1 ≤ a_i ≤ b_i ≤ n).
Utdata
Du ska skriva ut q rader med "ja" eller "nej", en för varje intervall. Raden ska innehålla "ja" om det är möjligt att placera ut noterna i intervallet a_i till b_i så att kraven är uppfyllda, annars "nej".
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
| Grupp | Poäng | Gränser |
|---|---|---|
| 1 | 25 | n,m,q ≤ 50 |
| 2 | 25 | n,m,q ≤ 5000 |
| 3 | 25 | m ≤ 5 |
| 4 | 25 | Inga ytterligare begränsningar |
Förklaring av exempelfall
I exempelfall 1 har vi bara tre strängar och kan därmed omöjligt representera sekvensen 1, 2, 2, 3, 4. Det gör att svaret blir nej för första och andra intervallet. Resten av intervallen går däremot att tilldela till strängar, t.ex. kan vi tilldela noterna i intervallet (1, 5) till strängarna 2, 1, 2, 2, 3.
I exempelfall 2 finns det bara en möjlig tilldelning av noter till strängar som funkar: 1, 2, 3, 1, 2, 3.
예제
예제 1
7 3 6 4 1 2 2 3 4 1 1 7 2 6 2 5 3 3 1 5 6 7
nej nej ja ja ja ja
예제 2
6 3 1 11 15 17 9 13 18 1 6
ja