想要n方过5e5吗
查看原帖
想要n方过5e5吗
239832
sipu6174楼主2020/5/29 21:03

那就帮我查错并开启O2吧

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,a[N],v[N],cnt,ans;
signed main(){
   cin>>n;
   for(int i=1;i<=n;i++){
      int x;cin>>x;
      if(x!=a[cnt]) a[++cnt]=x,v[cnt]=1;
      else v[cnt]++;
   }n=cnt;
   for(int i=1;i<=n;i++) ans+=v[i]*(v[i]-1)/2;
   for(int i=1;i<n;i++){
      int x=a[i],maxn=0;
      for(int j=i+1;j<=n&&maxn<=x;j++){
         if(a[j]>=maxn) ans+=a[i]<a[j]?v[i]:(a[i]==a[j]?v[i]*v[j]:v[j]);
         maxn=max(maxn,a[j]);
      }
   }cout<<ans;
   return 0;
}
2020/5/29 21:03
加载中...