fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define sz(a) (int)a.size()
  6. #define all(a) begin(a),end(a)
  7. #define int long long
  8.  
  9. const int mxN = (int)5e5+30;
  10.  
  11. int n, ans, tot;
  12. int a[mxN], b[mxN], pref[mxN];
  13.  
  14. template<int SZ>
  15. struct Fenwick{
  16. 	int fen[SZ+1]{0};
  17. 	void init(int n=SZ){
  18. 		for(int i = 1; i <= n; i++) fen[i]=0;
  19. 	}
  20. 	void upd(int x, int v){
  21. 		for(++x; x<=SZ; x+=x&-x) fen[x]+=v;
  22. 	}
  23. 	int sum(int x){
  24. 		int s = 0;
  25. 		for(++x; x>0; x-=x&-x) s+=fen[x];
  26. 		return s;
  27. 	}
  28. };
  29.  
  30. Fenwick<mxN> fen1, fen2;
  31.  
  32. void solve(){
  33. 	cin >> n;
  34. 	for(int i = 1; i <= n; i++){
  35. 		cin >> a[i]; int x = 0;
  36. 		while(a[i]%10==0) a[i]/=10,x++;
  37. 		ans+=i*(n-i+1)*x;
  38. 		while(a[i]%2==0) a[i]/=2,b[i]++;
  39. 		while(a[i]%5==0) a[i]/=5,b[i]--;
  40. 	}
  41. 	ans*=2;
  42. 	for(int i = 1; i <= n; i++){
  43. 		ans+=abs(b[i])*i*(n-i+1);
  44. 		pref[i] = pref[i-1]+b[i];
  45. 	}
  46.  
  47. 	vector<int> v;
  48. 	for(int i = 0; i <= n; i++) v.pb(pref[i]);
  49. 	sort(all(v)); v.erase(unique(all(v)),end(v));
  50. 	for(int i = 0; i <= n; i++) 
  51. 		pref[i]=(int)(lower_bound(all(v),pref[i])-begin(v));
  52.  
  53. 	for(int i = 1; i <= n; i++){
  54. 		ans-=abs(v[pref[i]]);
  55. 		int cnt = fen1.sum(pref[i]);
  56. 		int sum = fen2.sum(pref[i]);
  57. 		ans-=cnt*v[pref[i]]-sum;
  58. 		ans-=tot-sum-(i-1-cnt)*v[pref[i]];
  59. 		fen1.upd(pref[i],1);
  60. 		fen2.upd(pref[i],v[pref[i]]);
  61. 		tot+=v[pref[i]];
  62. 	}
  63. 	cout << ans/2 << "\n";
  64. }
  65.  
  66. int32_t main(){
  67. 	ios_base::sync_with_stdio(false); cin.tie(0);
  68. 	int t=1; while(t--) solve();
  69. }
Success #stdin #stdout 0.01s 9800KB
comments (?)
stdin 
7
10 2 5 4 5 6 7
stdout 
35
https://ideone.com/gffnrW
language:
C++14 (gcc 8.3)
created:
8 days 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!