#P6398. 「JOISC 2021 Day3」保镖

    ID: 5887 传统题 25000ms 1024MiB 尝试: 6 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS坐标变换离散化网格 DP离线查询直线上包络单调栈二分查找

「JOISC 2021 Day3」保镖

题目描述

JOI 街是一条贯通东西的长街。我们将其抽象为一条数轴。

从现在起,将有 NN 个贵宾(VIP)来到 JOI 街并大逛特逛。VIP 们以 11 到 NN 编号。VIP i (1≤i≤N)i\ (1 \le i \le N) 将会在时刻 TiT_i 从坐标 AiA_i 前往坐标 BiB_i。其速度是每单位时间 11 单位长度。
如果 Ai<BiA_i < B_i,VIP ii 将会以不变的速度在正方向上移动。类似地,如果 Ai>BiA_i > B_i,VIP ii 将会以不变的速度在负方向上移动。

一个保镖的工作是在 JOI 街上巡逻并保护 VIP 们。为了保护一个 VIP,很有必要和 TA 一起逛一会街,同时保护 TA。当然,允许保镖在他们逛街逛到一半时才开始保护,或在他们逛街结束前就停止保护。开始和停止保护的时刻不必为一个整数。
特别地,尽管可能有多个 VIP 在同一坐标,保镖也最多只能保护一个 VIP。

保镖可以在 JOI 街上以每单位时间最多 11 单位长度的速度随意走动。在他们停止保护一个 VIP 之后,可以去到另一个地方再开始保护另一个 VIP。如果一个保镖和 VIP ii 一起逛街,那么 VIP 将会对他们一起走过的距离的每单位长度给保镖 CiC_i 元小费。这里保证 CiC_i 是偶整数。

作为一个安保公司的员工,您正在计划 QQ 份保护 VIP 的方案。这些方案以 11 到 QQ 编号。对于方案 j (1≤j≤Q)j\ (1 \le j \le Q),一个保镖在时刻 PjP_j 时从坐标 XjX_j 开始工作。您的任务是分别最大化每个方案中的保镖能够得到的总小费。

请您编写一个程序对于给定的 VIP 和保镖的信息,计算每一个方案中保镖的最大总小费。

在此题的限制下,可以证明答案一定是个整数。

输入格式

第一行,两个整数 N,QN,Q。
以下 NN 行,每行四个整数 Ti,Ai,Bi,CiT_i,A_i,B_i,C_i。
以下 QQ 行,每行两个整数 Pj,XjP_j,X_j。

输出格式

输出 QQ 行到标准输出。第 j (1≤j≤Q)j\ (1 \le j \le Q) 行应当包含一个整数表示方案 jj 中保镖能得到的最大总小费。

数据范围

对于所有数据,满足

  • 1≤N≤2 8001 \le N \le 2\,800。
  • 1≤Q≤3 000 0001 \le Q \le 3\,000\,000。
  • 1≤Ti≤1 000 000 000 (1≤i≤N)1 \le T_i \le 1\,000\,000\,000\ (1 \le i \le N)。
  • 1≤Ai≤1 000 000 000 (1≤i≤N)1 \le A_i \le 1\,000\,000\,000\ (1 \le i \le N)。
  • 1≤Bi≤1 000 000 000 (1≤i≤N)1 \le B_i \le 1\,000\,000\,000\ (1 \le i \le N)。
  • 1≤Ci≤1 000 000 000 (1≤i≤N)1 \le C_i \le 1\,000\,000\,000\ (1 \le i \le N)。
  • Ai≠Bi (1≤i≤N)A_i \ne B_i\ (1 \le i \le N)。
  • 1≤Ci≤1 000 000 000 (1≤i≤N)1 \le C_i \le 1\,000\,000\,000\ (1 \le i \le N)。
  • CiC_i 是偶整数 (1≤i≤N)(1 \le i \le N)。
  • 1≤Pj≤1 000 000 000 (1≤j≤Q)1 \le P_j \le 1\,000\,000\,000\ (1 \le j \le Q)。
  • 1≤Xj≤1 000 000 000 (1≤j≤Q)1 \le X_j \le 1\,000\,000\,000\ (1 \le j \le Q)。

各子任务分值及限制见下表:

子任务编号 分值 限制
11 66 Ti≤3 000T_i \le 3\,000,Ai≤3 000A_i \le 3\,000,Bi≤3 000 (1≤i≤N)B_i \le 3\,000\ (1 \le i \le N),Pj≤3 000P_j \le 3\,000,Xj≤3 000 (1≤j≤Q)X_j \le 3\,000\ (1 \le j \le Q)
22 77 Q=1Q=1
33 1515 Q≤3 000Q \le 3\,000
44 2020 Q≤40 000Q \le 40\,000
55 5252 -
2 2
1 2 1 4
3 1 3 2
1 2
3 3
8
2
3 2
3 1 5 2
1 4 1 4
4 2 4 4
2 2
6 3
15
0
5 5
8 1 4 10
8 3 7 6
1 4 6 2
3 9 5 4
6 1 9 6
7 6
6 8
1 3
9 4
2 4
30
27
48
30
48