C. 人工湖

    传统题 1000ms 256MiB

人工湖

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点。最终,FJ 决定建一个人工湖供奶牛消暑之用。为了使湖看起来更加真实,FJ 决定将湖的横截面建成 NN 个连续的平台高低错落的组合状,所有的平台从左到右按 1∼N1\sim N 依次编号。当然咯,在湖中注入水后,这些平台都将被淹没。平台 ii 在设计图上用它的宽度 WiW_i 和高度(你可以理解为该平台顶离 FJ 挖的地基的高度)HiH_i 来描述的。所有平台的高度都是独一无二的。湖的边缘可以视为无限高的平台。下面给出了一张 FJ 的设计图:

         *            *  :
         *            *  :
         *            *  8
         *    **      *  7
         *    **      *  6
         *    **      *  5
         *    *********  4 <- height
         *    *********  3
         **************  2
         **************  1
Level     |1 |2|  3  |

按 FJ 的设想,在坑挖好后,他会以 11 单位每分钟的速度往最低的那个平台上注水。水在离开水管后立即下落,直到撞到平台顶或是更早些时候注入的水。然后,与所有常温下的水一样,它会迅速地流动、扩散。简单起见,你可以认为这些都是在瞬间完成的。FJ 想知道,对于每一个平台,它的顶部是从哪个时刻开始,与水面的距离至少为 11 单位长度。

WATER              WATER OVERFLOWS                     
       |                       |                           
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************
     After 4 mins        After 26 mins       After 50 mins

     Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged

输入格式

第一行一个正整数 NN。

下面 NN 行,每行两个正整数 Wi,HiW_i,H_i。

输出格式

NN 行,每行一个正整数,表示:对于每一个平台,它的顶部是从哪个时刻开始,与水面的距离至少为 11 单位长度。

输入输出样例 #1

输入 #1

3
4 2
2 7
6 4

输出 #1

4
50
26

数据范围

1≤N≤105;1≤Wi≤103;1≤Hi≤1061 ≤ N ≤ 10^5;1 ≤ W_i ≤10^3;1 ≤ H_i ≤ 10^6

2026-10-15

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-10-15 7:40
结束于
2026-10-15 12:00
持续时间
4.3 小时
主持人
参赛人数
6