루미 알고리즘

#1447다이아Guitar Hero

PO 2018 훈련 캠프코딩출제 Fredrik Hernqvist스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GruppPoängGränser
125n,m,q ≤ 50
225n,m,q ≤ 5000
325m ≤ 5
425Inga 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

출처 표기

출처: Programmeringsolympiaden 2018년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.