Canada Day Contest 2021 - Half Heart

View as PDF

Submit solution


Points: 25
Time limit: 20.0s
Memory limit: 1G

Authors:
Problem types

rpeng is trying to turn this into a canonical 2D rage problem, so we're going to set TL = 2 * runtime of fastest solution. You can help us set TL by either submitting faster solutions, or send in more test cases. rpeng promises that if the TL goes under 1s at some point, he will bring 3-D rage problems onto Dmojistan.

Deruikong is a highly skilled Minecraft player. Just as he had finished his great wool masterpiece, n black holes suddenly appeared and started destroying everything! Acting fast, Deruikong started collecting his blocks so that he could rebuild elsewhere. However, some of the blocks were already too close for him to collect without the risk of getting sucked in. The safeness of any location (X,Y,Z) is the minimum of \max(X-x_j,Y-y_j,Z-z_j) over all black holes j such that X \ge x_j, Y \ge y_j, Z \ge z_j, or -1 if no such hole exists. With only 1 hp left, Deruikong needs you to calculate the safeness of each block's location before everything is lost!

No 2 black holes are in the same location.

Input Specification

The first line contains two space-separated integers, n and q.

The next n lines contain three integers each, x_i, y_i, and z_i, the location of the ith black hole.

The next q lines contain three integers each, X_i, Y_i, and Z_i, the location of the ith block.

Output Specification

Provide the safeness of each block.

Constraints

1 \le n,q \le 500\,000

0 \le x_i, y_i, z_i, X_i, Y_i, Z_i \le 60\,000\,000

Sample Input 1

2 3
0 0 0
0 0 5
0 0 0
0 0 3
0 0 4

Sample Output 1

0
3
4

Sample Input 2

2 3
3 3 3
1 1 1
2 2 2
1 2 3
3 2 1

Sample Output 2

1
2
2

Sample Input 3

10 20
46902718 25907663 2878588
55735284 12603537 17470826
15981164 4340213 30136790
12018166 54408596 4435091
51715241 17349849 9656981
31709224 5992219 3823640
42153581 36646304 20195084
18012024 544896 8847160
53763337 3122454 57847793
3107443 19744160 1555718
8841107 20692456 40306182
2041879 33969394 20142890
36288293 48250270 20094855
42248889 34199313 57466914
21423927 40904396 30821857
39819710 7106627 5551137
41214546 36964634 24167718
17588623 9552541 52684010
15446397 42049027 9722824
19557164 43110839 11030939
30170944 55585276 31039047
49995090 36365705 35810198
43633569 56772072 2969715
36995652 35410194 45776812
43642245 53215913 58119326
1526616 52807672 52655983
28271301 32195317 31621432
51009822 32275518 46385152
23370956 47063794 16904853
53692856 35595834 4179859

Sample Output 3

38750464
-1
33180850
29859100
29266139
8110486
30972415
22547220
22304867
23366679
26603956
31986558
40526126
31069981
37924242
-1
27855104
35028658
27319634
9688171

Comments


  • 2
    Timsei  commented on June 28, 2023, 4:37 p.m.

    There's an another approach to this problem with time complexity O(nlog^2) (with huge constant) and memory complexity O(m).

    The idea is to convert the problem into 2-D RMQ problem.

    Firstly, we enumerate the order of size relationship between (X-x_j), (Y-y_j), and (Z-z_j).

    Wlog, (X-x_j) \leq (Y-y_j) \leq (Z-z_j)

    Then the condition would be 0 \leq (X-x_j) \leq (Y-y_j) \leq (Z-z_j). Those conditions can be further converted into x_j \leq X, Y-X \leq y_j - x_j, Z - Y \leq z_j - y_j which is a 2-D RMQ problem! We can work that out in O(nlog^2n) with CDQ and BIT.


  • 9
    rpeng  commented on Aug. 6, 2021, 6:55 p.m.

    get 2 werk everyone... :P