Canada Day Contest 2021 - Half Heart - DMOJ: Modern Online Judge

Canada Day Contest 2021 - Half Heart

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$ ~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)$ ~(X,Y,Z)~ is the minimum of $\max(X-x_j,Y-y_j,Z-z_j)$ ~\max(X-x_j,Y-y_j,Z-z_j)~ over all black holes $j$ ~j~ such that $X \ge x_j, Y \ge y_j, Z \ge z_j$ ~X \ge x_j, Y \ge y_j, Z \ge z_j~, or $-1$ ~-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$ ~n~ and $q$ ~q~.

The next $n$ ~n~ lines contain three integers each, $x_i$ ~x_i~, $y_i$ ~y_i~, and $z_i$ ~z_i~, the location of the $i$ ~i~th black hole.

The next $q$ ~q~ lines contain three integers each, $X_i$ ~X_i~, $Y_i$ ~Y_i~, and $Z_i$ ~Z_i~, the location of the $i$ ~i~th block.

Output Specification

Provide the safeness of each block.

Constraints

$1 \le n,q \le 500\,000$ ~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

Sample Output 1

0
3
4

Sample Input 2

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

Comments

2

Timsei commented on June 28, 2023, 4:37 p.m. ← edited →

There's an another approach to this problem with time complexity $\mathcal{O}(n \log^2 n)$ ~\mathcal{O}(n \log^2 n)~ (with huge constant) and memory complexity $\mathcal{O}(m)$ ~\mathcal{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)$ ~(X-x_j)~, $(Y-y_j)$ ~(Y-y_j)~, and $(Z-z_j)$ ~(Z-z_j)~.

Wlog, $(X-x_j) \leq (Y-y_j) \leq (Z-z_j)$ ~(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 $\mathcal{O}(n \log^2 n)$ ~\mathcal{O}(n \log^2 n)~ with CDQ and BIT.

9

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

get 2 werk everyone... :P