| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 80 | 26 | 25 | 33.333% |
La Paz, the capital city of Bolivia, is famous as a tourist spot and for an aerial cable car called Mi Teleférico. You are now visiting La Paz for sightseeing, and you want to visit as many sightseeing places as possible. In this task, we consider the following simplified situation.
There are $N$ aerial cable car stations in La Paz, numbered from 1ドル$ to $N$ in ascending order of altitude. There are $M$ one-way lines, numbered from 1ドル$ to $M$. There are $P$ aerial cable car companies, numbered from 1ドル$ to $P$. Each line is managed by a single company. Line $i$ (1ドル ≤ i ≤ M$) is operated from station $A_i$ to station $B_i,ドル and is managed by the company $C_i$. Here, the line always runs from the lower altitude station to the higher altitude station. In other words, $A_i < B_i$ holds.
The Bureau of transportation of La Paz issued unlimited ride passes for convenience. Each ride pass contains 2ドル$ integers $l,ドル $r,ドル which satisfy 1ドル ≤ l ≤ r ≤ P$. The pass enables the possessor to ride lines, which are managed by any one of company $l, l + 1, \dots ,r$. In other words, for an integer $i$ which satisfies 1ドル ≤ i ≤ M,ドル the pass enables the possessor to ride line $i$ when $l ≤ C_i ≤ r$ holds. It is possible to use a single pass for several lines. Let a ride pass $(l,r)$ denote this ride pass.
Now, $Q$ tourists, numbered from 1ドル$ to $Q,ドル visit La Paz. Tourist $j$ (1ドル ≤ j ≤ Q$) has a ride pass $(L_j, R_j)$ and $X_j$ boliviano cash.
Each tourist’s goal is to ensure that no station cannot be travelled from station 1ドル,ドル using only lines that can be ridden with the ride pass he or she has. Tourist $j$ (1ドル ≤ j ≤ Q$) can exchange his or her ride pass described in the following process to achieve their goal. Here, each tourist can exchange at most once.
Your purpose is to determine, for each tourist, whether or not he or she can achieve his or her goal within the cash he or she has.
Write a program which, given information about stations, lines, and tourists, determines whether or not he or she can achieve his or her goal within the cash he or she has for each tourist.
Read the following data from the standard input.
$N$ $M$ $P$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$
$Q$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$\vdots$
$L_Q$ $R_Q$ $X_Q$
Write $Q$ lines to the standard output. On the $j$-th line (1ドル ≤ j ≤ Q$), output Yes if tourist $j$ can achieve his or her goal, and No otherwise.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $N ≤ 50,ドル $M ≤ 50,ドル $Q ≤ 50,ドル $X_j = 0$ (1ドル ≤ j ≤ Q$). |
| 2 | 8 | $P ≤ 10$. |
| 3 | 11 | $P ≤ 100$. |
| 4 | 23 | $P ≤ 300,円 000,ドル $X_j = 0$ (1ドル ≤ j ≤ Q$). |
| 5 | 9 | $P ≤ 300,円 000$. |
| 6 | 22 | $N ≤ 8,円 000,ドル $M ≤ 8,円 000$. |
| 7 | 20 | No additional constraints. |
4 6 10 1 2 3 2 4 7 1 2 6 2 3 5 3 4 2 3 4 8 4 3 7 0 5 6 0 3 4 0 1 9 0
Yes No No Yes
First, tourist 1ドル$ has a ride pass $(3, 7)$ and 0ドル$ boliviano cash initially. He or she can achieve his or her goal without exchange. Because, this pass enables tourist 1ドル$ to ride 4ドル$ lines, lines 1ドル,ドル 2ドル,ドル 3ドル,ドル 4ドル,ドル and he or she can move to each stations from station 1ドル$ by using these 4ドル$ lines as follows.
Therefore, output Yes on the 1ドル$-st line.
Next, tourist 2ドル$ has a ride pass $(5, 6)$ and 0ドル$ boliviano cash initially. However, He or she can’t achieve his or her goal. Because, this pass enables tourist 2ドル$ to ride 2ドル$ lines, lines 3ドル,ドル 4ドル,ドル and he or she can’t move station 4ドル$ from station 1ドル$ by using these 2ドル$ lines. Moreover, since tourist 2ドル$ has only 0ドル$ boliviano as cash, he or she can’t exchange the pass with another pass.
Hence, output No on the 2ドル$-nd line.
Also, tourist 3ドル$ can’t achieve his or her goal, and tourist 4ドル$ can achieve his or her goal. Thus, output No on the 3ドル$-rd line, and output Yes on the 4ドル$-th line.
This sample input satisfies the constraints of all the Subtasks.
4 6 10 1 2 3 2 4 7 1 2 6 2 3 5 3 4 2 3 4 8 3 5 6 10 3 4 1 7 8 3
Yes No Yes
The information of stations and lines is the same as in the sample Input 1.
First, tourist 1ドル$ has a ride pass $(5, 6)$ and 10ドル$ boliviano cash initially. He or she can achieve his or her goal with exchange as below.
Therefore, output Yes on the 1ドル$-st line.
Next, tourist 2ドル$ has a ride pass $(3, 4)$ and 1ドル$ boliviano cash initially. He or she can’t achieve his or her goal with any exchange.
Consequently, output No on the 2ドル$-nd line.
Since Tourist 3ドル$ can achieve his or her goal, output Yes on the 3ドル$-rd line.
This sample input satisfies the constraints of Subtasks 2, 3, 5, 6, 7.
3 1 1000000000 1 2 6 1 1 1000000000 1000000000
No
It is not possible to move from station 1ドル$ to station 3ドル$ with these lines, so tourists can’t achieve their goal regardless of their ride passes.
This sample input satisfies the constraints of Subtasks 6, 7.
5 9 2000 2 3 1814 2 3 457 1 2 1226 3 4 1354 1 5 1050 1 2 1725 2 3 1383 1 5 1626 1 4 1795 5 850 1872 128 82 428 1217 487 924 573 1639 1926 202 202 420 25
Yes Yes Yes Yes No
This sample input satisfies the constraints of Subtasks 5, 6, 7.