TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3768
  • 题目
  • P3768数列操作
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 1000ms
    问题描述

    给出N个正整数数列a[1..N],再给出一个正整数k,现在可以重复进行如下操作:
    每次选择一个大于k的正整数a[i],将a[i]减去1,选择a[i-1]或a[i+1]中的一个加上1。
    经过一定次数的操作后,问最大能够选出多长的一个连续子序列,使得这个子序列的每个数都不小于k。
    总共给出M次询问,每次询问给出的k不同,你需要分别回答。

    输入格式

    第一行两个正整数N (N <= 300,000)和M (M <= 50)。
    第二行N个正整数,第i个正整数表示a[i] (a[i] <= 10^9)。
    第三行M个正整数,第i个正整数表示第i次询问的k (k <= 10^9)。

    输出格式

    共一行,输出M个正整数,第i个数表示第i次询问的答案。

    样例输入 1

    5 6
    1 2 1 1 5
    1 2 3 4 5 6

    样例输出 1

    5 5 2 1 1 0

    样例输入 2

    15 6
    10 3 2 2 3 10 4 2 2 1 10 1 1 1 1
    5 3 4 6 1 7

    样例输出 2

    6 15 12 2 15 2


    来源  Poi2010 blocks