2025-ho-t3_Mi_Teleférico — JOI JOI
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 20
Algorithms: graph theory, data structures, line sweep, segment tree, directed acyclic graph, two pointers

![](_page_0_Picture_0.jpeg)

# Mi Teleférico

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<sub>i</sub>* to station *B<sub>i</sub>*, and is managed by the company *C<sub>i</sub>*. Here, the line always runs from the lower altitude station to the higher altitude station. In other words, *A<sub>i</sub>* < *B<sub>i</sub>* 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, ..., *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<sub>i</sub>* ≤ *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<sub>j</sub>*, *R<sub>j</sub>*) and *X<sub>j</sub>* 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.

- He or she chooses 2 integers *l'*, *r'*, which satisfy 1 ≤ *l'* ≤ *r'* < *P*.
- He or she exchanges a ride pass (*L<sub>j</sub>*, *R<sub>j</sub>*) for a ride pass (*l'*, *r'*). It costs |*L<sub>j</sub>* − *l'*| + |*R<sub>j</sub>* − *r'*| boliviano as a fee.

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.

![](_page_1_Picture_0.jpeg)

#### Input

Read the following data from the standard input.

```
N M P
A1 B1 C1
A2 B2 C2
:
AM BM CM
Q
L1 R1 X1
L2 R2 X2
:
LQ RQ XQ
```

#### Output

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.

![](_page_2_Picture_0.jpeg)

### Constraints

*   2 ≤ *N* ≤ 300 000.
*   1 ≤ *M* ≤ 300 000.
*   1 ≤ *P* ≤ 10<sup>9</sup>.
*   1 ≤ *A<sub>i</sub>* < *B<sub>i</sub>* ≤ *N* (1 ≤ *i* ≤ *M*).
*   1 ≤ *C<sub>i</sub>* ≤ *P* (1 ≤ *i* ≤ *M*).
*   1 ≤ *Q* ≤ 400 000.
*   1 ≤ *L<sub>j</sub>* ≤ *R<sub>j</sub>* ≤ *P* (1 ≤ *j* ≤ *Q*).
*   0 ≤ *X<sub>j</sub>* ≤ 10<sup>9</sup> (1 ≤ *j* ≤ *Q*).
*   Given values are all integers.

### Subtasks

1.  (7 points) *N* ≤ 50, *M* ≤ 50, *Q* ≤ 50, *X<sub>j</sub>* = 0 (1 ≤ *j* ≤ *Q*).
2.  (8 points) *P* ≤ 10.
3.  (11 points) *P* ≤ 100.
4.  (23 points) *P* ≤ 300 000, *X<sub>j</sub>* = 0 (1 ≤ *j* ≤ *Q*).
5.  (9 points) *P* ≤ 300 000.
6.  (22 points) *N* ≤ 8 000, *M* ≤ 8 000.
7.  (20 points) No additional constraints.

![](_page_3_Picture_0.jpeg)

### Sample Input and Output

#### Sample Input 1

| Input         | Output |
|---------------|--------|
| 4 6 10        | Yes    |
| 1 2 3         | No     |
| 2 4 7         | No     |
| 1 2 6         | Yes    |
| 2 3 5         |        |
| 3 4 2         |        |
| 3 4 8         |        |
| 4             |        |
| 3 7 0         |        |
| 5 6 0         |        |
| 3 4 0         |        |
| 1 9 0         |        |

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 station from station 1 by using these 4 lines as follows.

*   It is possible to move as station 1 → 2 by using line 3.
*   It is possible to move as station 1 → 2 → 3 by using lines 1, 4 in this order.
*   It is possible to move as station 1 → 2 → 4 by using lines 3, 2 in this order.

Therefore, output `Yes` on the 1st 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 2nd 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 3rd line, and output `Yes` on the 4th line.

This sample input satisfies the constraints of all the Subtasks.

![](_page_4_Picture_0.jpeg)

#### Sample Input 2

| Input         | Output |
|---------------|--------|
| 4 6 10        | Yes    |
| 1 2 3         | No     |
| 2 4 7         | Yes    |
| 1 2 6         |        |
| 2 3 5         |        |
| 3 4 2         |        |
| 3 4 8         |        |
| 3             |        |
| 5 6 10        |        |
| 3 4 1         |        |
| 7 8 3         |        |

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.

1.  He or she chooses 2 integers *l'* = 1, *r'* = 5, which satisfy 1 ≤ *l'* ≤ *r'* < *P*.
2.  He or she exchanges a ride pass (5, 6) for a ride pass (1, 5). It costs |5 − 1| + |6 − 5| = 5 boliviano as a fee.

Therefore, output `Yes` on the 1st 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 2nd line.

Since Tourist 3 can achieve his or her goal, output `Yes` on the 3rd line.

This sample input satisfies the constraints of Subtasks 2, 3, 5, 6, 7.

#### Sample Input 3

| Input                   | Output |
|-------------------------|--------|
| 3 1 1000000000          | No     |
| 1 2 6                   |        |
| 1                       |        |
| 1 1000000000 1000000000 |        |

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.

![](_page_5_Picture_0.jpeg)

#### Sample Input 4

| Input          | Output |
|----------------|--------|
| 5 9 2000       | Yes    |
| 2 3 1814       | Yes    |
| 2 3 457        | Yes    |
| 1 2 1226       | Yes    |
| 3 4 1354       | No     |
| 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     |        |

This sample input satisfies the constraints of Subtasks 5, 6, 7.

Starter code: