Guest User

Untitled

a guest
Jul 5th, 2019
2,090
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. int main() {
  7.  
  8. int n;
  9. cin>>n;
  10. vector<int> a(n);
  11. for (int i = 0; i<n; i++) cin>>a[i];
  12.  
  13. vector<vector<pair<int, int>>> dp(20);
  14. int cur = 1;
  15. for (int i = 0; i<n; i++) dp[0].push_back(make_pair(a[i], 0));
  16. for (int deg = 1; deg<20; deg++)
  17. {
  18. cur*=2;
  19. for (int i = 0; i+cur<=n; i++)
  20. {
  21. int left1 = dp[deg-1][i].first;
  22. int left2 = dp[deg-1][i+cur/2].first;
  23. int candies1 = dp[deg-1][i].second;
  24. int candies2 = dp[deg-1][i+cur/2].second;
  25. int res_candies = candies1 + candies2;
  26. int res_left = (left1 + left2)%10;
  27. if (left1+left2>=10) res_candies++;
  28. dp[deg].push_back(make_pair(res_left, res_candies));
  29. }
  30. }
  31. int q;
  32. cin>>q;
  33. int l, r;
  34. for (int i = 0; i<q; i++)
  35. {
  36. cin>>l>>r;
  37. int len = (r-l+1);
  38. int deg = 0;
  39. while (len%2==0) {deg++; len/=2;}
  40. cout<<dp[deg][l-1].second<<endl;
  41. }
  42. }
RAW Paste Data