oj.uz

Submission #170345

# Submission time Handle Problem Language Result Execution time Memory
170345 2019-12-24T20:19:14 Z ngmh Sterilizing Spray (JOI15_sterilizing) C++11
5 / 100
 5000 ms 13936 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
        long long  s, e, m, v;
        node *l, *r;
	node(long long _s, long long _e){
		s = _s; e = _e; m = (s+e)/2; v = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void point_update(long long x, long long y){
		if(s == e){ v = y; return; }
		if(x > m) r->point_update(x, y);
		if(x <= m) l->point_update(x, y);
		v = l->v+r->v;
	}
	void range_update(long long x, long long y, long long k){
		if(s == e){ v /= k; return; }
		if(x > m) r->range_update(x, y, k);
		else if(y <= m) l->range_update(x, y, k);
		else { l->range_update(x, m, k); r->range_update(m+1, y, k); }
		v = l->v+r->v;
	}
	long long range_query(long long x, long long y){
		if(s == x && e == y) return v;
		if(x > m) return r->range_query(x, y);
		if(y <= m) return l->range_query(x, y);
		return l->range_query(x, m)+r->range_query(m+1, y);
        }
} *root;

long long n, q, o, a, b, c;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q >> c;
	root = new node(1, n);
	for(int i = 1; i <= n; i++){
		cin >> a;
		root->point_update(i, a);
	}
	for(int i = 0; i < q; i++){
		cin >> o;
		if(o == 1){
			cin >> a >> b;
			root->point_update(a, b);
		} else if(o == 3){
			cin >> a >> b;
			cout << root->range_query(a, b) << "\n";
		} else {
			cin >> a >> b;
			root->range_update(a, b, c);
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 10 ms 632 KB Output is correct
5 Correct 19 ms 888 KB Output is correct
6 Correct 19 ms 888 KB Output is correct
7 Correct 18 ms 760 KB Output is correct
8 Correct 18 ms 888 KB Output is correct
9 Correct 19 ms 760 KB Output is correct
10 Correct 19 ms 888 KB Output is correct
11 Correct 19 ms 888 KB Output is correct
12 Correct 20 ms 760 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 1996 KB Output is correct
2 Correct 1080 ms 6364 KB Output is correct
3 Correct 1695 ms 6648 KB Output is correct
4 Correct 3885 ms 4860 KB Output is correct
5 Execution timed out 5096 ms 13936 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 5013 ms 8940 KB Time limit exceeded
2 Halted 0 ms 0 KB -