fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pii pair<int,int>
  6. #define ll long long
  7. #define N (int)(2e5+10)
  8. #define mod 1000000007
  9. #define mp make_pair
  10. #define pb push_back
  11. #define nd second
  12. #define st first
  13. #define inf mod
  14. #define endl '\n'
  15. #define sag (sol|1)
  16. #define sol (root<<1)
  17. #define ort ((bas+son)>>1)
  18. #define bit(x,y) ((x>>y)&1)
  19. #define int long long
  20.  
  21. ll A[N],St[4*N];
  22. int i,j,k,n,m,x,y,z;
  23. int L[4*N],mn[4*N],a[N],L1[N],L2[N];
  24. int R1[N],R2[N],mx[4*N];
  25.  
  26. void upd(int root,int bas,int son,int x,int y,int t){
  27.    if(bas > y or son < x or mn[root] >= t)
  28.       return;
  29.  
  30.    if(x <= bas and son <= y and mx[root] <= t){
  31.       St[root] = (ll)t*(son-bas+1);
  32.       mx[root] = mn[root] = L[root] = t;
  33.       return;
  34.    }
  35.  
  36.    if(L[root]){
  37.       mx[sol] = mx[sag] = mn[sol] = mn[sag] = L[sol] = L[sag] = L[root];
  38.       St[sol] = (ll)L[root]*(ort-bas+1);
  39.       St[sag] = (ll)L[root]*(son-ort);
  40.       L[root] = 0;
  41.    }
  42.  
  43.    upd(sol,bas,ort,x,y,t);
  44.    upd(sag,ort+1,son,x,y,t);
  45.  
  46.    mn[root] = min(mn[sol] , mn[sag]);
  47.    mx[root] = max(mx[sol] , mx[sag]);
  48.    St[root] = St[sol] + St[sag];
  49. }
  50.  
  51. main(){
  52.    cin >> n;
  53.  
  54.    for(i=1 ; i<=n ; i++){
  55.       scanf("%lld",a+i);
  56.  
  57.       int x = sqrt(a[i]);
  58.  
  59.       for(j=1 ; j<=x ; j++)
  60.          if(a[i]%j == 0){
  61.             if(!L1[j])
  62.                L1[j] = i;
  63.             else if(!L2[j]){
  64.                L2[j] = i;
  65.             }
  66.             R2[j] = R1[j];
  67.             R1[j] = i;
  68.  
  69.             if(j*j!=a[i]){
  70.  
  71.                if(!L1[a[i]/j])
  72.                   L1[a[i]/j] = i;
  73.                else if(!L2[a[i]/j]){
  74.                   L2[a[i]/j] = i;
  75.                }
  76.                R2[a[i]/j] = R1[a[i]/j];
  77.                R1[a[i]/j] = i;
  78.             }
  79.          }
  80.    }
  81.  
  82.    for(i=1 ; i<=n ; i++)
  83.       upd(1,1,n,i,i,i);
  84.  
  85.    for(i=2e5+1 ; i>=1 ; i--){
  86.       if(L1[i] != R1[i]){
  87.          upd(1,1,n,1,L1[i],R2[i]);
  88.          upd(1,1,n,L1[i]+1,L2[i],R1[i]);
  89.          upd(1,1,n,L2[i]+1,n,n+1);
  90.       }
  91.       A[i] = (ll)n*(n+1) - St[1];
  92.    }
  93.  
  94.    ll ans = 0;
  95.  
  96.    for(i=1 ; i<=2e5 ; i++)
  97.       ans += (A[i+1]-A[i])*i;
  98.  
  99.    cout << ans << endl;
  100. }
Success #stdin #stdout 0s 37800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/MyQfZz
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!