Kaaleppi's run

#include <stdio.h> // include before iostream for faster scanf
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <tuple>
#include <utility>
#include <iomanip>
#include <iterator>

using namespace std;
typedef long long LL;

#define printv(printVec) for (auto printVecIter : (printVec)) cout << printVecIter << " "; cout << endl;

// g++-4.8 -Wall -Wshadow -std=c++11 a.cpp && ./a.out

int SZ = 1000;

int main() {
	std::ios::sync_with_stdio(false);cin.tie(0);
	int n, q;
	cin >> n>>q;
	typedef pair<int,int> pii;
	typedef priority_queue<pii, vector<pii>> pq;

	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	//vector<vector<pair<int,int>>> sq(n/SZ + 2);
	vector<pq> sq(n/SZ + 2);
	vector<LL> sums(n/SZ + 2);
	for (int i = 0; i < n; i++) {
		sq[i/SZ].emplace(v[i],i);
		sums[i/SZ] += v[i];
	}

	while (q--) {
		int type; cin >> type;
		if (type == 2) {
//cout<<endl;
//printv(v);
			int l,r; cin>>l>>r; l--; r--;
			LL ans = 0;
			for (int i = l; i <= r; i++) {
				if (i + SZ < r && (i % SZ) == 0) {
					int block = i / SZ;
					ans += sums[block];
					i += SZ - 1;
				} else {
					ans += v[i];
				}
			}
			cout << ans <<"\n";
			continue;
		}

		int l,r,k; cin>>l>>r>>k; l--;r--;
		for (int i = l; i <= r; i++) {
			if (i + SZ < r && (i % SZ) == 0) {
				int block = i / SZ;
				while (sq[block].top().first >= k || v[sq[block].top().second] >= k) {
//cout <<q<<" "<<i << " " << sq[block].top().first << " MODIFyING " << sq[block].top().second <<endl; 
					int val, idx;
					tie(val, idx) = sq[block].top();
					sq[block].pop();
					sums[block] -= v[idx];
					v[idx] = v[idx] % k;
					sums[block] += v[idx];
					sq[block].emplace(v[idx], idx);
//cout <<sq[block].size() << " "<<sq[block].top().first << " NEWTOP " << sq[block].top().second <<endl; 
				}
				i += SZ - 1;
			} else {
				sums[i/SZ] -= v[i];
				v[i] = v[i] % k;
				sums[i/SZ] += v[i];
			}
		}
		
	}
	
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED