比赛场次 | 513 |
---|---|
比赛名称 | EYOI暨SBOI暑假快乐赛3rd |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2022-06-27 08:30:00 |
结束时间 | 2022-06-27 12:00:00 |
开放分组 | 全部用户 |
注释介绍 | EYOI暨SBOI2022暑假的第三场比赛! 暑假热身赛第三,题都不是很难哦! 细心审题,尽力拿到可以拿到的分数! 注意题目难度不是按照题目编号依次递增! |
题目名称 | Convoluted Intervals |
---|---|
输入输出 | Convoluted_Intervals.in/out |
时间限制 | 3000 ms (3 s) |
内存限制 | 256 MiB |
测试点数 | 20 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
遥时_彼方 | AAAAAAAAAAAAAAAAAAAA |
0.854 s | 0.00 MiB | 100 |
yrtiop | AAAAAAAAAAAAAAAAAAAA |
1.447 s | 0.00 MiB | 100 |
ムラサメ | AAAAAAAAAAAAAAAAAAAA |
1.536 s | 0.00 MiB | 100 |
康尚诚 | AAEEEEEEEEEEEEEEEEEE |
3.325 s | 0.00 MiB | 10 |
该账号已注销 | AATTTWTWTTTWTWWWTWTW |
33.381 s | 0.00 MiB | 10 |
lihaoze | AATTTTWWWWTTTWWTTTWT |
34.603 s | 0.00 MiB | 10 |
cb | AWWAWTTTTTTTTTTTTTTT |
46.196 s | 0.00 MiB | 10 |
┭┮﹏┭┮ | AATTTTTTTTTTTTTTTTTT |
54.000 s | 0.00 MiB | 10 |
ZRQ | AATTTTTTTTTTTTTTTTTT |
54.000 s | 0.00 MiB | 10 |
lavey | AATTTTTTTTTTTTTTTTTT |
54.000 s | 0.00 MiB | 10 |
nick | AATTTTTTTTTTTTTTTTTT |
54.002 s | 0.00 MiB | 10 |
Convoluted_Intervals.in
输出文件:Convoluted_Intervals.out
简单对比奶牛们正在努力尝试发明有趣的新游戏来玩。他们目前的工作之一与一组 $N$ 个区间($1 \leq N \leq 2 \times 10^5$)有关,其中第 $i$ 个区间从数轴上的 $a_i$ 位置开始,并在位置 $b_i \geq a_i$ 结束 $a_i$ 和 $b_i$ 均为 $0 \dots M$ 范围内的整数,其中 $1 \leq M \leq 5000$。这个游戏的玩法是,Bessie 选择某个区间(假设是第 $i$ 个区间),而她的表妹 Elsie 选择某个区间(假设是第 $j$ 个区间,可能与 Bessie 所选的的区间相同)。给定某个值 $k$,如果 $a_i + a_j \leq k \leq b_i + b_j$,则她们获胜。
对范围 $0 \dots 2M$ 内的每个值 $k$,请计算使得 Bessie 和 Elsie 可以赢得游戏的有序对 $(i,j)$ 的数量。
输入的第一行包含 $N$ 和 $M$。以下 $N$ 行每行以整数 $a_i$ 和 $b_i$ 的形式描述一个区间。
输出 $2M+1$ 行,依次包含范围 $0 \dots 2M$ 中的每一个 $k$ 的答案。
2 5 1 3 2 5
0 0 1 3 4 4 4 3 3 1 1
在这个例子中,对于 $k=3$,有三个有序对可以使得 Bessie 和 Elsie 获胜:$(1,1)$,$(1,2)$,和 $(2,1)$。
测试点 $1-2$ 满足 $N \leq 100,M \leq 100$。
测试点 $3-5$ 满足 $N \leq 5000$。
测试点 $6-20$ 没有额外限制。
注意输出可能无法用 $32$ 位整数型存储,你可能需要使用 $64$ 位整数型(例如,C 或 C++ 中的 "long long")。
USACO 2021.12 银组第三题