AtCoder Beginner Contest 038 C - 単調増加

今回の ABC は久しぶりにちょっと難しかったです。

問題

abc038.contest.atcoder.jp

解法

[l, r) の区間が単調増加の場合, その間にある条件を満たすペアの数は (r-l)*(r-l+1)/2 で求められます。各単調増加列ごとにこれを求めれば答えが得られます。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) 
        cin >> A[i];
    ll ans = 0;
    for (int i = 0; i < N; ) {
        int j = i+1;
        while (j < N && A[j] > A[j-1]) j++;
        ll len = j-i;
        ans += len*(len+1)/2;
        i = j;
    }
    cout << ans << endl;
    return 0;
}