| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 30 | 10 | 10 | 41.667% |
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:
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?
Den första raden innehåller tre heltal $n,ドル $m$ och $q$ (1ドル \leq n, m, q \leq 10^5$). Den andra raden innehåller $n$ heltal $t_i$ (1ドル \leq t_i \leq 10^9$). Sen följer $q$ rader med två heltal $a_i$ och $b_i$ vardera (1ドル \leq a_i \leq b_i \leq n$).
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".
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
Eftersom vi bara har tre strängar kan vi 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$.
Olympiad > Swedish Olympiad in Informatics > 2018 > KATT 2 B번