406872: GYM102586 L Yosupo's Algorithm

Can you replicate my master thesis in 5 hours?

You are given $$$N$$$ red points and $$$N$$$ blue points on a two dimensional plane. The $$$i$$$-th red point's coordinate is $$$(r^x_i, r^y_i)$$$, and its weight is $$$r^w_i$$$. The $$$i$$$-th blue point's coordinate is $$$(b^x_i, b^y_i)$$$, and its weight is $$$b^w_i$$$.

Process $$$Q$$$ queries. In the $$$i$$$-th query, you are given two integers $$$L_i$$$ and $$$R_i$$$, and choose a red point $$$j$$$ and a blue point $$$k$$$ with following conditions:

• $$$r^y_j < b^y_k$$$
• ($$$r^x_j < L_i$$$ and $$$R_i < b^x_k$$$) or ($$$L_i < r^x_j$$$ and $$$b^x_k < R_i$$$)

Your task is to maximize the sum of weights of the two points or report that it is impossible to select two points.

Input is given from Standard Input in the following format:

$$$N$$$

$$$r^x_1$$$ $$$r^y_1$$$ $$$r^w_1$$$

$$$\vdots$$$

$$$r^x_N$$$ $$$r^y_N$$$ $$$r^w_N$$$

$$$b^x_1$$$ $$$b^y_1$$$ $$$b^w_1$$$

$$$\vdots$$$

$$$b^x_N$$$ $$$b^y_N$$$ $$$b^w_N$$$

$$$Q$$$

$$$L_1$$$ $$$R_1$$$

$$$\vdots$$$

$$$L_Q$$$ $$$R_Q$$$

Constraints:

• $$$1 \leq N \leq 100{,}000$$$
• $$$1 \leq Q \leq 500{,}000$$$
• $$$-1{,}000{,}000{,}000 \leq r^x_i, L_i \leq -1$$$
• $$$1 \leq b^x_i, R_i \leq 1{,}000{,}000{,}000$$$
• $$$1 \leq r^y_i, b^y_i \leq 1{,}000{,}000{,}000$$$
• $$$1 \leq r^w_i, b^w_i \leq 1{,}000{,}000{,}000$$$
• $$$r^x_1,\cdots,r^x_N,b^x_1,\cdots,b^x_N,L_1,\cdots,L_Q,R_1,\cdots,R_Q$$$ are all distinct
• $$$r^y_1,\cdots,r^y_N,b^y_1,\cdots,b^y_N,$$$ are all distinct
• All values in input are integers.

For each query, in a line, print the maximum sum of weights of the selected points, or $$$-1$$$ if it is impossible to choose two points.

2
-3 1 1
-6 3 10
3 4 100
5 2 1000
5
-5 4
-2 6
-4 1
-10 10
-1 2

101
-1
110
1001
1001

10
-389 786 414303478
-159 301 976196121
-268 599 754785437
-605 652 597104844
-199 841 214521748
-192 8 581825989
-515 898 509582353
-297 36 854072992
-489 616 41481895
-665 876 378086770
869 583 376652629
509 222 380009514
354 693 428231281
519 738 608396032
100 811 220629740
960 708 928349711
324 89 710139852
716 897 771429659
647 203 72269757
368 699 540753047
10
-350 499
-956 639
-287 504
-915 742
-777 135
-176 487
-150 987
-133 10
-852 147
-476 106

1564212844
1584592153
1782422703
1747625780
1196825861
1782422703
-1
1904545832
1196825861
1525454555