P2311 loidc,想想看

    • 137通过
    • 332提交
  • 题目提供者 千反田爱瑠
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    话说loidc现在正在家闲的无聊,这天loidc正在观看比赛,他突然很有兴趣想了解一段时间内中国队获得金牌的情况。

    题目描述

    还有一点,loidc有特殊能力,可以预知未来,他可以准确的猜到中国队在某一个单位时间内获得的金牌数。但是,还有但是!由于工作量太大,再加上猜金牌要费很多的体力,所以他无法准确的计算出一段时间内获得的金牌数最大的单位时间是哪个,就因为这样loidc很郁闷。他思索来思索去就想到了你,因为他知道你是个OIer,所以他对你呵呵一笑就把问题交给你了,loidc希望你能在1S内得出答案

    输入输出格式

    输入格式:

    第一行一个n表示有n个时间段。

    接下来一行有n个数ai,ai表示loidc猜到的中国队在第i个时间段内获得的金牌数。

    然后,第三行有一个数m,表示loidc有个问题。

    接下来有m行,每行有2个数分别为xi yi,表示要询问在时间段[xi,yi]内中国队获得金牌数最大的是哪个单位时间。

    loidc有一个习惯,他问问题是有先后的,也就是说后一个问题总是在前一个问题之后提出的。

    注意对于第i个提问和第i+1个提问严格的有xi<=xi+1,yi<=yi+1。

    输出格式:

    一共m行,每行一个ki,表示第i个询问的答案。

    输入输出样例

    输入样例#1: 复制
    5
    2 3 4 5 6
    5
    1 1
    1 2
    2 3
    3 4
    4 5
    
    输出样例#1: 复制
    1
    2
    3
    4
    5
    

    说明

    30%: n<=1000 m<=1000

    100%: n<=100000 m<=100000

    其他有关输入输出均小于maxlongint。

    数据保证ai没有相同的。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。