#P3022. [Balkan2012]The Best Teams

    ID: 2154 传统题 1500ms 128MiB 尝试: 54 已通过: 19 难度: 8 上传者: 标签>难度分类提高+/省选-贪心排序贪心交换论证排序与序列处理离散化离线与分治离线查询查询排序模拟与实现技巧状态机模拟数据结构普通线段树线段树上二分CF2400

[Balkan2012]The Best Teams

[BalkanOI 2012] The Best Teams

题目描述

选拔员 Srba 要为 BOlympic Games 2012 的每场比赛组建队伍。他有 NN 名选手可供选择,并知道每名选手的年龄和能力值。队伍的能力值为所有入选选手的能力值之和。

能力相近的选手不能同时入选。所有选手的能力值互不相同。若没有第三名选手的能力值严格介于两名选手之间,则这两名选手能力相近。用全部 NN 名选手按能力值排序,能力相近的选手正好是排序后相邻的选手。

共有 TT 场比赛。每场比赛有年龄上限 AA 和队员人数上限 KK。队伍中每名选手的年龄都不得超过 AA,人数不得超过 KK。各场比赛独立选人,同一名选手可以参加多场比赛。

对每场比赛,求组出的队伍的最大能力值。空队伍的能力值为 00。

输入格式

第一行一个整数 NN。接下来 NN 行,第 ii 行包含两个整数 Agei,SkilliAge_i,Skill_i,分别表示第 ii 名选手的年龄和能力值。

随后一行一个整数 TT。接下来 TT 行,第 ii 行包含两个整数 Ai,KiA_i,K_i,分别表示第 ii 场比赛的年龄上限和人数上限。

输出格式

输出 TT 行,按输入顺序逐场输出队伍的最大能力值。请使用 6464 位整数。

数据范围

1≤N,T≤3000001\le N,T\le300000,1≤Agei,Skilli≤1091\le Age_i,Skill_i\le10^9,所有选手的能力值互不相同。

  • 30%30\% 的测试满足 N≤5000N\le5000。

样例

7
17 21
24 36
14 19
27 20
21 50
18 5
33 7
4
20 3
50 2
99 5
10 2
45
71
95
0

样例解释

能力相近的选手对为 (6,7),(7,3),(3,4),(4,1),(1,2),(2,5)(6,7),(7,3),(3,4),(4,1),(1,2),(2,5)。前三场比赛各自的最优队伍依次为 {1,3,6}\{1,3,6\}、{1,5}\{1,5\}、{1,3,5,6}\{1,3,5,6\}。第四场比赛的年龄上限为 1010,没有选手符合要求。

原题 PDF