比赛 2024暑假C班集训5 评测结果 AAWWWWWWWW
题目名称 充电宝 最终得分 20
用户昵称 123 运行时间 0.265 s
代码语言 C++ 内存使用 94.09 MiB
提交时间 2024-07-05 09:57:59
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=200010,M=5050;
int n,a[N],b[M][M],flag[N];
long long ret=0;
int main() {
    freopen("charger.in","r",stdin);
    freopen("charger.out","w",stdout);
    cin>>n;
    if (n>5000)
    {
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        cout<<n*(n-1)/2;
        return 0;
    }
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]); 
        b[a[i]][i]++;
    }
    for (int i=1;i<=n;i++)
    {
        if (flag[a[i]]) continue;
        for (int j=1;j<=n;j++)
        {
            b[a[i]][j]+=b[a[i]][j-1];
        }
        flag[a[i]]=1;
    }
    for (int i=1;i<=n-1;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            if (a[i]!=a[j] && b[a[i]][j-1]==b[a[i]][i] && b[a[j]][j-1]==b[a[j]][i])
            {
                ret++;
            }
        } 
    }
    cout<<ret;
}