#HX1252C. 信息学团体赛

提交19 通过13
通过率68.4%
时间限制1000ms
内存限制128MiB
    ID: 10037 传统题 1000ms 128MiB 尝试: 19 已通过: 13 难度: 普及 上传者: 标签>二分算法编程题C++CSPCSP复赛CSP复赛专项练习暑假CSP复赛集训暑假集训1252-二分优化

题目描述

题目描述

信息赛是一项竞赛活动,其比赛形式主要包括个人赛和团体赛。在团体赛中,参赛者需要组成团队,共同完成一系列编程题目,并进行有效的协作沟通。

有一种团队赛形式是由恰好三名选手组成一个团队参加。刘老师作为珅泽教育学校的信息学教练,决定让自己机构的学生参加此次比赛。但由于比赛中的题目均为英文描述,因此仅凭编程能力很难获胜。

已知刘老师的社团有 n 名学生,其中第 i 名选手的编程能力为 aia_i,英文阅读能力为 bib_i,而他们的综合能力可通过该公式计算:⌊ai×60%+bi×40%a_i\times 60\%+b_i\times 40\%⌋,其中 ⌊ ⌋ 表示向下取整。

刘老师决定选出 3 名学生代表学校去参加本次比赛。为了不让团队中选手的实力过于悬殊,他希望选出的 3 名选手相互之间的综合能力之差不能超过k。如果无法完成组队,则输出−1。

请你帮助刘老师计算一下,在不考虑学生相互之间的先后顺序的情况下,一共有多少种组队方式。

输入格式

第一行,包含两个正整数 n,k。

第二行,包含 n 个正整数 a1a_{1},a2a_{2},…,ana_n,表示每名学生的编程能力。

第三行,包含 n 个正整数 b1b_{1},b2b_{2},…,bnb_n,表示每名学生的英文阅读能力。

对于 100% 数据:1n2×105,1ai,bi,k1091\le n\le 2\times 10^{5},1\le a_i,b_i,k\le 10^{9}

输出格式

一行,包含一个整数,表示结果

样例输入

5 4
4 5 1 10 6
2 9 1 8 5

样例输出

3

提示

对于 30% 数据:1n200,1ai,bi,k1031\le n\le 200,1\le a_i,b_i,k\le 10^{3}

对于 60% 数据:1n2×103,1ai,bi,k1061\le n\le 2\times 10^{3},1\le a_i,b_i,k\le 10^{6}

对于 100% 数据:1n2×105,1ai,bi,k1091\le n\le 2\times 10^{5},1\le a_i,b_i,k\le 10^{9}

1 1
1
1
-1
2 25
6 15
5 9
-1
1 1  
1  
1
-1