fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
  6. #define dbg(x) cerr << (#x) << " --> " << (x) << endl
  7.  
  8. #define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
  9. #define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
  10. #define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
  11.  
  12. #define type(x) __typeof(x.begin())
  13.  
  14. #define orta (bas + son >> 1)
  15. #define sag (k + k + 1)
  16. #define sol (k + k)
  17.  
  18. #define pb push_back
  19. #define mp make_pair
  20.  
  21. #define nd second
  22. #define st first
  23.  
  24. #define endl '\n'
  25.  
  26. typedef pair < int ,int > pii;
  27.  
  28. typedef long long ll;
  29.  
  30. const long long linf = 1e18+5;
  31. int mod = (int) 1e9 + 7;
  32. const int logN = 18;
  33. const int inf = 1e9;
  34. const int N = 2e5 + 5;
  35.  
  36. int n, m, x, y, z, a[N];
  37. vector< int > H[N], v[N];
  38. ll sum = 0, ans[N];
  39.  
  40. set< pair< pii , int > > S;
  41.  
  42. void divide(int x) {
  43.     set< pair< pii , int > > :: iterator it, it2;
  44.     it = S.lower_bound(mp(mp(x + 1, 0), -1));
  45.     if(it == S.begin()) return ; it--;
  46.     if(it->st.nd < x) return ;
  47.     pair< pii , int > t = *it; S.erase(*it);
  48.     S.insert(mp(mp(t.st.st, x), t.nd));
  49.     if(x + 1 <= t.st.nd) S.insert(mp(mp(x + 1, t.st.nd), t.nd));
  50. }
  51.  
  52. void remove(int x) {
  53.     divide(x - 1);
  54.     while(S.rbegin()->st.st >= x) {
  55.         pair< pii , int > t = *S.rbegin();
  56.         sum -= (t.st.nd - t.st.st + 1) * (ll) (t.nd);
  57.         S.erase(S.find(t));
  58.     }
  59. }
  60.  
  61. void maximize(set< pair< pii , int > > :: iterator it, int x, int y) {
  62.     pair< pii , int > t; t.nd = x; t.st.st = y;
  63.     set< pair< pii , int > > :: iterator it2;
  64.     while(it != S.end()) {
  65.         if(it->nd >= x) break;
  66.         t.st.nd = it->st.nd;
  67.         sum -= (it->st.nd - it->st.st + 1) * (ll) (it->nd);
  68.         it2 = it; it2++; S.erase(it); it = it2;
  69.     }
  70.     if(t.st.st <= t.st.nd) {
  71.         sum += (t.st.nd - t.st.st + 1) * (ll) t.nd;
  72.         S.insert(t);
  73.     }
  74. }
  75.  
  76. int main() {
  77.  
  78.     scanf("%d", &n);
  79.  
  80.     FOR(i, 1, n) {
  81.         scanf("%d", &a[i]);
  82.         H[a[i]].pb(i); sum += i;
  83.         S.insert(mp(mp(i, i), i));
  84.     }
  85.  
  86.     FOR(i, 1, N - 1)
  87.         for(int j = i; j < N; j += i)
  88.             foreach(it, H[j])
  89.                 v[i].pb(*it);
  90.  
  91.     ans[N - 1] = n * (ll) (n + 1) / 2;
  92.  
  93.     ROF(i, N - 2, 1) {
  94.         int l = v[i].size() - 1;
  95.         if(l <= 0) { ans[i] = ans[i + 1];  continue; }
  96.         sort(v[i].begin(), v[i].end()); remove(v[i][1] + 1);
  97.         maximize(S.begin(), v[i][l-1], 1);
  98.         divide(v[i][0]); maximize(S.lower_bound(mp(mp(v[i][0] + 1, v[i][0]), 0)), v[i][l], v[i][0] + 1);
  99.         ans[i] = (S.rbegin()->st.nd * (ll)(n + 1) - sum);
  100.     }
  101.  
  102.     ll all = 0;
  103.  
  104.     FOR(i, 1, N - 2) all += (ans[i + 1] - ans[i]) * (ll) i;
  105.  
  106.     printf("%lld\n", all);
  107.  
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0.03s 10496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QhwMPF
language:
C++ (gcc 8.3)
created:
8 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!