結果

問題 No.1525 Meximum Sum
ユーザー vjudge1
提出日時 2026-03-17 17:34:30
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 1,297 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,441 ms
コンパイル使用メモリ 334,284 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2026-03-17 17:34:36
合計ジャッジ時間 4,730 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<int> A(N+1), pos(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        pos[A[i]] = i; // l?u v? tr 1-based
    }

    ll ans = 0;
    // t?ng s? ?o?n = N*(N+1)/2 (dng n?u c?n cho mex=0 nh?ng contribution c?a 0 l 0)
    // X? l x = 0 ring (nh?ng v 0 * count0 = 0 nn khng ?nh h??ng ans).
    // Kh?i t?o L,R v?i v? tr c?a 0 (sau ? vng for x t? 1..N-1 dng L,R l range c?a 0..x-1)
    int L = pos[0], R = pos[0];

    for (int x = 1; x <= N-1; ++x) {
        // hi?n t?i L,R l min/max c?a pos[0..x-1]
        int px = pos[x];
        ll total_with_LR = (ll)L * (ll)(N - R + 1);
        ll include_px = (ll)min(L, px) * (ll)(N - max(R, px) + 1);
        ll count_x = total_with_LR - include_px;
        ans += (ll)x * count_x;
        // m? r?ng L,R ?? ch?a pos[x] cho l?n x+1
        L = min(L, px);
        R = max(R, px);
    }

    // tr??ng h?p mex = N: ?o?n ph?i ch?a t?t c? 0..N-1, t?c ch?a [L,R] v?i L,R hi?n t?i (sau vng)
    // s? ?o?n ch?a [L,R] l L * (N - R + 1)
    ll cntN = (ll)L * (ll)(N - R + 1);
    ans += (ll)N * cntN;

    cout << ans << '\n';
    return 0;
}
0