AT_abc484_e.Subsegment Sum Finder

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a sequence A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N) of length NN. Find the number of (non-empty) contiguous subsequences whose sum is between LL and RR, inclusive.
Here, even if two contiguous subsequences are equal as sequences, they are counted separately if they are taken from different positions.

给你一个长度为 NN 的序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N)。求和在 LL 到 RR 之间(含端点)的(非空)连续子序列的个数。
注意:即使两个连续子序列作为序列完全相同,只要它们起始或结束位置不同,就视为不同的子序列,分别计数。

输入格式

The input is given from Standard Input in the following format:

NN LL RR
A1A_1 A2A_2 …\dots ANA_N

输入从标准输入中按以下格式给出:

NN LL RR
A1A_1 A2A_2 …\dots ANA_N

输出格式

Print the answer.

输出答案。

输入输出样例

  • 输入#1

    5 -2 3
    3 -1 -4 -1 5

    输出#1

    8
  • 输入#2

    6 0 0
    0 0 0 0 0 0

    输出#2

    21
  • 输入#3

    10 -126566 92319
    11087 76694 -94782 -28589 -77903 -75549 31253 60353 -69062 -49587

    输出#3

    34

说明/提示

Sample 1 Explanation:
For this input, there are 88 pairs (l,r)(l,r) such that the contiguous subsequence from the ll-th through rr-th elements satisfies the condition:

  • (1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)(1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)

Sample 2 Explanation:
It is possible that L=RL=R.

Constraints

  • All input values are integers.
  • 1≤N≤3×1051 \le N \le 3 \times 10^5
  • −1018≤L≤R≤1018-10^{18} \le L \le R \le 10^{18}
  • −1012≤Ai≤1012-10^{12} \le A_i \le 10^{12}

样例 1 解释:
对于该输入,共有 88 对 (l,r)(l,r),使得从第 ll 个元素到第 rr 个元素的连续子序列满足题目条件:

  • (1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)(1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)

样例 2 解释:
有可能出现 L=RL=R 的情况。

约束条件

  • 所有输入值均为整数。
  • 1≤N≤3×1051 \le N \le 3 \times 10^5
  • −1018≤L≤R≤1018-10^{18} \le L \le R \le 10^{18}
  • −1012≤Ai≤1012-10^{12} \le A_i \le 10^{12}

输入解题思路,AI测评打分。不知道怎么写?

首页