読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

AtCoder Beginner Contest 038 C - 単調増加

解法

単調増加する区間毎に分ける。
長さnの区間が含む長さ1以上の区間の個数は、総和の公式を使ってn*(n+1)/2。

実装

バグってたけど何も考えずに番兵を置いたら通った。
番兵はいいぞ。

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int MAX_N = 100000;
 
int N, A[MAX_N + 1];
 
int TotalSum(int n)
{
	return n*(n + 1)/2;
}
 
signed main()
{
	cin >> N;
	int cnt = 0, ans = 0;
	A[N] = -LLONG_MAX;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	for (int i = 0; i < N; i++)
	{
		cnt++;
		if (A[i] >= A[i + 1]) ans += TotalSum(cnt), cnt = 0;
	}
	printf("%lld\n", ans);
	return 0;
}