NOI '19 P4 - Jump

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

There are n cities in Byteland numbered from 1 to n and city 1 is the capital. All cities' locations are on a w \times h grid, which has an integer coordinate (x,y) (1 \le x \le w, 1 \le y \le h). Different cities share different locations.

There are m portals in Byteland numbered from 1 to m. Portal i is located at city p_i, with some constraints t_i,L_i,R_i,D_i,U_i. With portal i, Kevin can spend t_i (t_i > 0) transporting from p_i to a city j where its location (x,y) satisfies L_i \le x \le R_i, D_i \le y \le U_i (1 \le L_i \le R_i \le w, 1 \le D_i \le U_i \le h). One city may have many portals.

Starting from city 1, Kevin wants to know the least time needed to go to every city i. Note that Kevin can only transport with portals and only using portals take time. It is guaranteed that there is at least a way to go to each city i from city 1.

Input Specification

The first line contains four integers n,m,w,h.

In the following n lines, each line contains two integers x_i,y_i, indicating the coordinate of city i.

In the following m lines, each line contains six integers p_i,t_i,L_i,R_i,D_i,U_i, indicating constraints of portal i.

Constraints

For all test cases, 1 \le n \le 70\,000, 1 \le m \le 150\,000, 1 \le w,h \le n, 1 \le t_i \le 10\,000.

Test Case1 \le n \le1 \le m \leAdditional Constraints
1~8100100None
9~1350\,000100\,000Every portal can reach exactly 1 city, and L_i = R_i, D_i=U_i
14~1850\,000100\,000h = 1
19~2225\,00050\,000None
23~2570\,000150\,000

Output Specification

In line i, output the answer to city i+1.

Sample Input 1

5 3 5 5
1 1
3 1
4 1
2 2
3 3
1 123 1 5 1 5
1 50 1 5 1 1
3 10 2 2 2 2

Sample Output 1

50
50
60
123

Comments

There are no comments at the moment.