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; }