요수포의 알고리즘

...Can you replicate my master thesis in 5 hours?

---

Yosupo

2차원 평면 위에 $N$개의 빨간 점과 $N$개의 파란 점이 주어진다. $i$번째 빨간 점의 좌표는 $(r^x_i, r^y_i)$이고 가중치는 $r^w_i$이다. $i$번째 파란 점의 좌표는 $(b^x_i, b^y_i)$이고 가중치는 $b^w_i$이다.

$Q$개의 질의를 처리한다. $i$번째 질의에서는 두 정수 $L_i$와 $R_i$가 주어진다. 아래 조건을 만족하는 빨간 점 $j$와 파란 점 $k$를 고른다.

• $r^y_j < b^y_k$
• ($r^x_j < L_i$이고 $R_i < b^x_k$) 또는 ($L_i < r^x_j$이고 $b^x_k < R_i$)

고른 두 점의 가중치 합을 최대로 만들고, 두 점을 고를 수 없으면 그 사실을 보고한다.

입력은 표준 입력으로 다음 형식에 따라 주어진다.

$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$

각 질의마다 고른 점들의 가중치 합의 최댓값을 한 줄에 출력한다. 두 점을 고를 수 없으면 $-1$을 출력한다.

• $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$은 모두 서로 다르다
• $r^y_1,\cdots,r^y_N,b^y_1,\cdots,b^y_N$은 모두 서로 다르다