提出 #62114918

---

ソースコード 拡げる

#include<bits/stdc++.h>

using namespace std;

typedef long long i64;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> pos(n + 1);
    for(int i = 0; i <= n; i++) {
        pos[i].push_back(0);
    }
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for(int i = 0; i <= n; i++) {
        pos[i].push_back(n + 1);
    }

    i64 ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < (int)pos[i].size() - 1; j++) {
            auto it = upper_bound(pos[i - 1].begin(), pos[i - 1].end(), pos[i][j]);
            int lst = max(pos[i][j - 1], *prev(it));
            int nxt = *it;
            i64 add = 1LL * (nxt - pos[i][j]) * (pos[i][j] - lst);
            ans += add;
            // cerr << i << ' ' << j << ' ' << add << '\n';
        }
    }

    cout << ans << '\n';

    return 0;
}

提出情報

ジャッジ結果