Submission #170345

#	Time	Username	Problem	Language	Result	Execution time	Memory
170345		ngmh	Sterilizing Spray (JOI15_sterilizing)	C++11	5 / 100	5096 ms	13936 KiB

sterilizing

#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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75