oj.uz

Submission #124825

# Submission time Handle Problem Language Result Execution time Memory
124825 2019-07-04T03:20:52 Z DMCS Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 2252 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 p) {
	if(l > p || r < p) return; 
	if(l == r) {
		it[id] /= k;
		return;
	}
	
	int m = (l+r)/2;
	dec(id*2, l, m, p);
	dec(id*2+1, m+1, r, p);
	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;		
			for(int i = l; i <= r; i++) dec(1, 1, n, i);
		}
		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 7 ms 376 KB Output is correct
2 Correct 11 ms 376 KB Output is correct
3 Correct 7 ms 248 KB Output is correct
4 Correct 42 ms 504 KB Output is correct
5 Correct 94 ms 504 KB Output is correct
6 Correct 98 ms 504 KB Output is correct
7 Correct 93 ms 504 KB Output is correct
8 Correct 92 ms 596 KB Output is correct
9 Correct 98 ms 504 KB Output is correct
10 Correct 99 ms 504 KB Output is correct
11 Correct 95 ms 560 KB Output is correct
12 Correct 100 ms 504 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2882 ms 1172 KB Output is correct
2 Execution timed out 5011 ms 2108 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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