fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. ll modPow(ll a, ll b){
  9. 	if(b == 0)return 1;
  10. 	ll g = modPow(a, b / 2);
  11. 	g *= g;
  12. 	g %= MOD;
  13. 	if(b & 1)g *= a;
  14. 	g %= MOD;
  15. 	return g;
  16. }
  17.  
  18. void solve(){
  19. 	int n;
  20. 	cin >> n;
  21. 	vector<ll> a(n);
  22.  
  23. 	for(int i = 0;i < n; i++){
  24. 		cin >> a[i];
  25. 	}
  26.  
  27. 	ll sum = 0;
  28. 	multiset<pair<int, ll>> s;
  29.  
  30. 	for(int i = 0; i < n; i++){
  31. 		int cnt = 0;
  32. 		while(s.size()){
  33. 			auto [p, q] = *(s.begin());
  34. 			if(p <= a[i] || cnt >= 30 || ((1ll << cnt) * a[i]) >= p){
  35. 				s.erase(s.find({p, q}));
  36. 				ll g = modPow(2, q);
  37. 				g *= p;
  38. 				g %= MOD;
  39. 				sum -= g;
  40. 				if(sum < 0)sum += MOD;
  41. 				sum += p;
  42. 				sum %= MOD;
  43. 				cnt += q;
  44. 			}else break;
  45. 		}
  46.  
  47. 		while(a[i] % 2 == 0){
  48. 			cnt++;
  49. 			a[i] /= 2;
  50. 		}
  51. 		if(cnt > 0){
  52. 			s.insert({a[i], cnt});
  53. 		}
  54. 		// cout << cnt << " ";
  55. 		ll g = modPow(2, cnt);
  56. 		g *= a[i];
  57. 		g %= MOD;
  58. 		sum += g;
  59. 		sum %= MOD;
  60. 		cout << sum << " ";
  61.  
  62. 	}
  63. 	cout << "\n";
  64.  
  65. }
  66.  
  67. int main(){
  68. 	ios_base::sync_with_stdio(false);
  69. 	cin.tie(nullptr);
  70.  
  71. 	int t = 1;
  72. 	cin >> t;
  73.  
  74. 	for(int i = 1; i <= t; i++){
  75. 		solve();
  76. 	}
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
3
10
1 2 3 4 5 6 7 8 9 10
11
1 6 9 4 7 4 4 10 3 2 3
4
527792568 502211460 850237282 374773208
stdout
copy 
1 3 8 13 46 59 126 149 1174 1311 
1 7 22 26 70 74 150 1303 1306 1308 1568 
527792568 83665723 399119771 773892979
https://ideone.com/YbYzGv
language:
C++14 (gcc 8.3)
created:
4 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!