結果

問題 No.1526 Sum of Mex 2
ユーザー vjudge1
提出日時 2025-07-20 20:13:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,312 bytes
コンパイル時間 1,976 ms
コンパイル使用メモリ 199,748 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-20 20:13:34
合計ジャッジ時間 4,141 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
int n;
int a[100005];
int nxt[100005];
int dd[100005];
long long val;
long long ans=0;
int now[100005];
set<int>s;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n+1; i++)dd[i]=n+1;
    for(int i=n; i>=1; i--)nxt[i]=dd[a[i]],dd[a[i]]=i;
    int maxx=0;
    for(int i=1; i<=n+1; i++) {
        if(dd[i]>maxx) {
            maxx=dd[i];
            s.insert(i);
        }
        now[i]=dd[i];

    }
    int pre=1;
    for(auto it=s.begin(); it!=s.end(); it++) {
        val+=(*it)*(now[*it]-pre);
        pre=now[*it];
    }
    ans=val;
    for(int i=1; i<=n-1; i++) {
        if(now[*s.begin()]>i)
            val-=(*s.begin());
        auto it=s.lower_bound(a[i]);
        if(it==s.end()) {
            ans+=val;
            continue;
        }
        if(*it==a[i]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*next(it);
            if(now[a[i]]>=ll)
                val-=a[i]*(now[a[i]]-ll);
            val-=r*(now[r]-now[a[i]]);
            val+=r*(now[r]-ll);
            s.erase(it++);
        }
        now[a[i]]=nxt[i];
        while(next(it)!=s.end()&&now[a[i]]>now[*it]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*next(it);
            val-=(*it)*(now[*it]-ll);
            val-=r*(now[r]-now[*it]);
            val+=r*(now[r]-ll);
            s.erase(it++);
        }
        if(*it<a[i]) {
            ans+=val;
            continue;
        }
        if(now[a[i]]>=now[*it]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            val-=(*it)*(now[*it]-ll);
            val+=a[i]*(now[a[i]]-ll);
            s.erase(it);
        } else {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*it;
            val-=(*it)*(now[*it]-ll);
            val+=a[i]*(now[a[i]]-ll);
            val+=r*(now[r]-now[a[i]]);
        }
        s.insert(a[i]);
        ans+=val;
        //cout<<i<<" "<<val<<'\n';
    }
    cout<<ans;
    return 0;
}
0