Kaaleppi's run

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

#define ll long long
#define ld long double
#define ii pair<int,int>
#define si pair<string,int>
#define iii pair<int,ii>
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define msvs map<string,vs>
#define msi map<string,int>
#define mss map<string,int>
#define us unordered_set
#define um unordered_map
#define pq priority_queue
#define pb push_back
#define mp make_pair
#define forall(i,a,b) for (int i=a;i<b;i++)
#define foreach(v,c) for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a) a.begin(), a.end()
#define in(a,b) ( (b).find(a) != (b).end())
#define fill(a,v) memset(a, v, sizeof a)
#define sz(a) ((int)(a.size()))
#define N (1<<17)
#define M 1000000007
#define I 500000004

ll n,q;
ll p[2*N];

void muuta(int k, ll x) {
	k += N;
	p[k] = x;
	for (k /= 2; k >= 1; k /= 2) {
		p[k] = p[2*k]+p[2*k+1];
	}
}

ll summa(int a, int b) {
	a += N; b += N;
	ll s = 0;
	while (a <= b) {
		if (a%2 == 1) s += p[a++];
		if (b%2 == 0) s += p[b--];
		a /= 2; b /= 2;
	}
	return s;
}

int main()
{
	cin >> n >> q;
	ll t[n+1];
	for (int i = 0; i < n; i++) {
		cin >> t[i];
		muuta(i+1,t[i]);
	}
	for (int i = 0; i < q; i++) {
		int a,l,r; cin >> a;
		if (a == 1) {
			ll k; cin >> l >> r >> k;
			for (int j = l; j <= r; j++) {
				t[j-1] /= k;
				muuta(j,t[j-1]);
			}
		} else {
			int l,r;
			cin >> l >> r;
			cout << summa(l,r) << "\n";
		}
	}
	return 0;
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: TIME LIMIT EXCEEDED

Test 19

Verdict: TIME LIMIT EXCEEDED

Test 20

Verdict: TIME LIMIT EXCEEDED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: TIME LIMIT EXCEEDED