結果

問題 No.2956 Substitute with Average
ユーザー pockyny
提出日時 2025-07-14 02:34:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,317 ms / 3,000 ms
コード長 1,867 bytes
コンパイル時間 788 ms
コンパイル使用メモリ 90,212 KB
実行使用メモリ 139,284 KB
最終ジャッジ日時 2025-07-14 02:35:37
合計ジャッジ時間 34,303 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
typedef long long ll;
unordered_map<int,ll> um[40][40];
int a[200010],s[200010];
int main(){
    int i,j,k,n; cin >> n;
    for(i=1;i<=n;i++) cin >> a[i];
    ll ans = 0;
    s[0] = 0;
    for(i=1;i<=n + 2;i++) s[i] = s[i - 1] + a[i - 1];
    for(i=1;i<=n + 1;i++){
        // [l,i)で、平均がa[l - 1]でもa[i]でもないやつ
        ans += i - 1;
        for(j=0;j<=30;j++){
            // a[l - 1]==jのものについて数える
            // 平均がa[i]を引く
            int val1 = s[i] - i*a[i];
            if(um[j][a[i]].find(val1)!=um[j][a[i]].end()){
                ans -= um[j][a[i]][val1];
            }
            // 平均がjを引く
            int val2 = s[i] - i*j;
            if(a[i]!=j && um[j][j].find(val2)!=um[j][j].end()){
                ans -= um[j][j][val2];
            }
        }
        // for(int l=1;l<i;l++){
        //     if(s[l] - l*a[i]==s[i] - i*a[i]) ans--;
        //     else if(s[l] - l*a[l - 1]==s[i] - i*a[l - 1]) ans--;
        // }
        // cout << " i == " << i << " " << ans << " " << um[0][1][-1] << " " << s[i] - i*a[i] << "\n";
        for(j=0;j<=30;j++) um[a[i - 1]][j][s[i] - i*j]++;
    }
    // int deb = 0;
    // for(int l=1;l<=n;l++){
    //     for(int r=l + 1;r<=n + 1;r++){
    //         // [l,r)で条件を満たすやつ
    //         int sum = 0;
    //         for(i=l;i<r;i++) sum += a[i];
    //         if((r - l)*a[l - 1]!=sum && (r - l)*a[r]!=sum) deb++;
    //     }
    // }
    // cout << "ans == " << ans << " " << deb << "\n";
    vector<pair<int,ll>> v;
    for(i=1;i<=n;i++){
        if(v.size()==0 || v.back().first!=a[i]){
            v.push_back({a[i],1});
        }else{
            v.back().second++;
        }
    }
    ans -= v.size();
    ans++;
    cout << ans << "\n";
}
0