SHARE
TWEET

Untitled

a guest May 19th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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.  
  13. #pragma hdrstop
  14. #pragma argsused
  15.  
  16. using namespace std;
  17.  
  18.  
  19. int main() {
  20.     fstream str("output.txt",ios_base::in|ios_base::out|ios_base::trunc);
  21.     size_t n, m, s;
  22.     cin >> n;
  23.     if (n > 1000) {
  24.         s = 4*ceil(sqrt(n/3));
  25.     } else {
  26.         s = ceil(sqrt(n));
  27.     }
  28.     vector<size_t> buckets(n/s + 1);
  29.     vector<size_t> data(n + 1);
  30.     vector<size_t> out_buck(n + 1);
  31.     for (size_t i = 1; i < n + 1; ++i) {
  32.         cin >> data[i];
  33.     }
  34.     cin >> m;
  35.     for (size_t j = 0; j < m; ++j) {
  36.         char c; cin >> c;
  37.         if (c == '1') {
  38.             size_t i; cin >> i; size_t sqrt_i = size_t(sqrt(i));
  39.             size_t value = data[i];
  40.             for (size_t d = 1; d <= sqrt_i; ++d) {
  41.                 if (i % d == 0) {
  42.                     value +=out_buck[d];
  43.                     if (d%s == 0 && s != 1) {
  44.                         value += buckets[(d - 1)/s];
  45.                     } else {
  46.                         value += buckets[d/s];
  47.                     }
  48.                     if (i / d != d) {
  49.                         value +=out_buck[i/d];
  50.                         if ((i/d)%s == 0 && s != 1) {
  51.                             value += buckets[i/d/s - 1];
  52.                         } else {
  53.                             value += buckets[i/d/s];
  54.                         }
  55.                     }
  56.                 }
  57.             }
  58.             str << value << endl;
  59.         } else {
  60.             size_t l, r, d;
  61.             cin >> l >> r >> d;
  62.             while (l <= r) {
  63.                 if ((l-1)%s == 0 & (l + s - 1) <=r) {
  64.                     buckets[l/s]+= d;
  65.                     l += s;
  66.                 } else {
  67.                     out_buck[l] +=d;
  68.                     l++;
  69.                 }
  70.             }
  71.         }
  72.     }
  73.     return 0;
  74. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top