Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <set>
- #include <fstream>
- #include <cmath>
- #include <ios>
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- using namespace std;
- int main() {
- fstream str("output.txt",ios_base::in|ios_base::out|ios_base::trunc);
- size_t n, m, s;
- cin >> n;
- s = ceil(sqrt(n));
- vector<size_t> buckets(n/s + 1);
- vector<size_t> data(n + 1);
- vector<size_t> out_buck(n + 1);
- for (size_t i = 1; i < n + 1; ++i) {
- cin >> data[i];
- }
- cin >> m;
- for (size_t j = 0; j < m; ++j) {
- char c; cin >> c;
- if (c == '1') {
- size_t i; cin >> i; size_t sqrt_i = size_t(sqrt(i));
- size_t value = data[i];
- for (size_t d = 1; d <= sqrt_i; ++d) {
- if (i % d == 0) {
- value +=out_buck[d];
- if (d%s == 0 && s != 1) {
- value += buckets[(d - 1)/s];
- } else {
- value += buckets[d/s];
- }
- if (i / d != d) {
- value +=out_buck[i/d];
- if ((i/d)%s == 0 && s != 1) {
- value += buckets[i/d/s - 1];
- } else {
- value += buckets[i/d/s];
- }
- }
- }
- }
- str << value << endl;
- } else {
- size_t l, r, d;
- cin >> l >> r >> d;
- while (l <= r) {
- if ((l-1)%s == 0 & (l + s - 1) <=r) {
- buckets[l/s]+= d;
- l += s;
- } else {
- out_buck[l] +=d;
- l++;
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement