oj.uz

Submission #124834

# Submission time Handle Problem Language Result Execution time Memory
124834 2019-07-04T03:38:29 Z DMCS Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 3984 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t
const int N = 1e5+1;

int n, q, k;
int it[4*N], a[N];

void build(int id, int l, int r) {
	if(l == r) {
		it[id] = a[l]; 
		return;
	}
	
	int m = (l+r)/2;
	build(id*2, l, m);
	build(id*2+1, m+1, r);
	it[id] = it[id*2] + it[id*2+1];
}

void update(int id, int l, int r, int p, int val) {
	if(l > p || r < p) return; 
	if(l == r) {
		it[id] = val;
		return;
	}
	
	int m = (l+r)/2;
	update(id*2, l, m, p, val);
	update(id*2+1, m+1, r, p, val);
	it[id] = it[id*2] + it[id*2+1];
}

void dec(int id, int l, int r, int x, int y) {
	if(l > y || r < x) return; 
	if(l == r) {
		it[id] /= k;
		return;
	}
	
	int m = (l+r)/2;
	dec(id*2, l, m, x, y);
	dec(id*2+1, m+1, r, x, y);
	it[id] = it[id*2] + it[id*2+1];
}

int get(int id, int l, int r, int x, int y) {
	if(l > y || r < x) return 0;
	if(l >= x && r <= y) return it[id];
	
	int m = (l+r)/2;
	return get(id*2, l, m, x, y) + get(id*2+1, m+1, r, x, y);
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> q >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	build(1, 1, n); 
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			int p, val;
			cin >> p >> val;
			update(1, 1, n, p, val);
		}
		if(t == 2) {
			int l, r;
			cin >> l >> r;		
			dec(1, 1, n, l, r);
		}
		if(t == 3) {
			int l, r;
			cin >> l >> r;
			cout << get(1, 1, n, l, r) << endl;
		}
	}  
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 13 ms 536 KB Output is correct
5 Correct 22 ms 504 KB Output is correct
6 Correct 22 ms 504 KB Output is correct
7 Correct 21 ms 504 KB Output is correct
8 Correct 21 ms 504 KB Output is correct
9 Correct 22 ms 504 KB Output is correct
10 Correct 36 ms 504 KB Output is correct
11 Correct 23 ms 504 KB Output is correct
12 Correct 22 ms 504 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 3748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 1100 KB Output is correct
2 Correct 1181 ms 2168 KB Output is correct
3 Correct 1871 ms 2304 KB Output is correct
4 Correct 4130 ms 2460 KB Output is correct
5 Execution timed out 5033 ms 3984 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5006 ms 3736 KB Time limit exceeded
2 Halted 0 ms 0 KB -