26378번 - Z1 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
문제
Ivan smišlja šablonski zadatak za školsko natjecanje iz informatike. U tom zadatku je zadan niz brojeva S = a1, a2, . . . , an gdje vrijedi 0 ≤ aj < H i m upita oblika xj, yj gdje vrijedi 1 ≤ xj ≤ yj ≤ n. Odgovor na j-ti upit je najveći od brojeva u nizu S na pozicijama između xj i yj uključivo: zj = max(axj, axj+1, . . . , ayj).
Ivan je napravio odličan test podatak za ovaj zadatak, ali je izgubio originalni niz S. Zadana je duljina originalnog niza n, ograničenje na veličinu elemenata niza H, te m upita xj, yj zajedno s odgovorima na te upite zj. Niz S duljine n je dobar ako se sastoji od brojeva između 0 i H − 1 uključivo te je svaki zj ispravan odgovor na odgovarajući upit xj, yj. Odredite broj dobrih nizova S modulo 109 + 7.
입력
U prvom redu nalaze se prirodni brojevi n, m i H — duljina niza, broj upita i ograničenje na veličinu elemenata niza. U j-tom od sljedećih m redova nalaze se tri cijela broja xj, yj i zj (1 ≤ xj ≤ yj ≤ n, 0 ≤ zj < H) — j-ti upit te odgovor na njega.
출력
Ispišite jedan broj — traženi broj dobrih nizova modulo 109 + 7.
서브태스크
U svim podzadacima vrijedi 1 ≤ m, H ≤ 106.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | n ≤ 100 |
| 2 | 30 | n ≤ 1 000 |
| 3 | 50 | n ≤ 1 000 000 |
예제 입력 1
3 2 3 1 2 1 2 2 0
예제 출력 1
3
예제 입력 2
7 10 3 1 3 1 3 4 1 3 6 2 4 5 2 1 1 1 1 2 1 3 3 0 1 1 1 3 3 0 3 6 2
예제 출력 2
18
힌트
Pojašnjenje prvog primjera: Zbog drugog upita, element a2 mora biti 0 pa, stoga, zbog prvog upita element a1 mora biti 1. Element a3 može biti bilo koji nenegativni cijeli broj manji od H = 3. Stoga, svi dobri nizovi S su redom (1, 0, 0), (1, 0, 1) i (1, 0, 2).
채점 및 기타 정보
- 예제는 채점하지 않는다.