Advertisement
Guest User

Untitled

a guest
May 19th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <set>
  4. #include <fstream>
  5. #include <cmath>
  6. #include <ios>
  7. #pragma GCC optimize("Ofast")
  8. #pragma GCC optimize("no-stack-protector")
  9. #pragma GCC optimize("unroll-loops")
  10. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  11.  
  12. using namespace std;
  13.  
  14.  
  15.  
  16.  
  17. int main() {
  18.     fstream str("output.txt",ios_base::in|ios_base::out|ios_base::trunc);
  19.     size_t n, m, s;
  20.     cin >> n;
  21.         s = ceil(sqrt(n));
  22.     vector<size_t> buckets(n/s + 1);
  23.     vector<size_t> data(n + 1);
  24.     vector<size_t> out_buck(n + 1);
  25.     for (size_t i = 1; i < n + 1; ++i) {
  26.         cin >> data[i];
  27.     }
  28.     cin >> m;
  29.     for (size_t j = 0; j < m; ++j) {
  30.         char c; cin >> c;
  31.         if (c == '1') {
  32.             size_t i; cin >> i; size_t sqrt_i = size_t(sqrt(i));
  33.             size_t value = data[i];
  34.             for (size_t d = 1; d <= sqrt_i; ++d) {
  35.                 if (i % d == 0) {
  36.                     value +=out_buck[d];
  37.                     if (d%s == 0 && s != 1) {
  38.                         value += buckets[(d - 1)/s];
  39.                     } else {
  40.                         value += buckets[d/s];
  41.                     }
  42.                     if (i / d != d) {
  43.                         value +=out_buck[i/d];
  44.                         if ((i/d)%s == 0 && s != 1) {
  45.                             value += buckets[i/d/s - 1];
  46.                         } else {
  47.                             value += buckets[i/d/s];
  48.                         }
  49.                     }
  50.                 }
  51.             }
  52.             str << value << endl;
  53.         } else {
  54.             size_t l, r, d;
  55.             cin >> l >> r >> d;
  56.             while (l <= r) {
  57.                 if ((l-1)%s == 0 & (l + s - 1) <=r) {
  58.                     buckets[l/s]+= d;
  59.                     l += s;
  60.                 } else {
  61.                     out_buck[l] +=d;
  62.                     l++;
  63.                 }
  64.             }
  65.         }
  66.     }
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement