AT_abc485_g.Similar Adjacent Subarrays
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a sequence of positive integers A=(A1,A2,…,AN) of length N.
Find the number of triples of integers (a,b,c) that satisfy all of the following conditions.
- 0≤a<b<c≤N
- b−a=c−b
- There is exactly one integer i between 1 and b−a, inclusive, such that Aa+i=Ab+i.
给你一个长度为 N 的正整数序列 A=(A1,A2,…,AN)。
求满足以下所有条件的整数三元组 (a,b,c) 的个数:
- 0≤a<b<c≤N
- b−a=c−b
- 在 1 到 b−a(含端点)之间的整数 i 中,恰好存在一个使得 Aa+i=Ab+i。
输入格式
The input is given from Standard Input in the following format:
N
A1 A2 … AN
输入从标准输入中按以下格式给出:
N
A1 A2 … AN
输出格式
Print the answer in one line.
在一行中输出答案。
输入输出样例
输入#1
7 1 2 1 3 1 2 1
输出#1
10
输入#2
2 1000000000 1000000000
输出#2
0
输入#3
6 1 2 3 1 2 4
输出#3
6
说明/提示
Sample 1 Explanation:
The triples (a,b,c) that satisfy the conditions are the following ten: (0,1,2),(0,2,4),(1,2,3),(1,3,5),(2,3,4),(2,4,6),(3,4,5),(3,5,7),(4,5,6),(5,6,7).
Constraints
- 2≤N≤2×105
- 1≤Ai≤109
- All input values are integers.
样例 1 解释:
满足条件的三元组 (a,b,c) 共有以下十个:(0,1,2),(0,2,4),(1,2,3),(1,3,5),(2,3,4),(2,4,6),(3,4,5),(3,5,7),(4,5,6),(5,6,7)。
限制条件
- 2≤N≤2×105
- 1≤Ai≤109
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?