Submission #518887

#	Time	Username	Problem	Language	Result	Execution time	Memory
518887		amunduzbaev	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	375 ms	6184 KiB

sterilizing

#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 1e5 + 5;
struct ST{
	long long tree[N<<2];
	int mx[N<<2], mn[N<<2], f[N<<2];
	
	void push(int x, int lx, int rx){
		if(lx == rx || !f[x]) return;
		int m = (lx + rx) >> 1;
		mx[x<<1] = mx[x<<1|1] = mx[x];
		mn[x<<1] = mn[x<<1|1] = mx[x];
		tree[x<<1] = (m - lx + 1) * 1ll * mx[x];
		tree[x<<1|1] = (rx - m) * 1ll * mx[x];
		f[x<<1] = f[x<<1|1] = 1;
		f[x] = 0;
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = mn[x] = mx[x] = v; return; }
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = tree[x<<1] + tree[x<<1|1];
		mn[x] = min(mn[x<<1], mx[x<<1|1]);
		mx[x] = max(mx[x<<1], mx[x<<1|1]);
	}
	
	void div(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l || v == 1 || mx[x] == 0) return;
		if(lx >= l && rx <= r && (mx[x] / v) == (mn[x] / v)){
			mx[x] = mn[x] = mx[x] / v;
			tree[x] = (rx - lx + 1) * 1ll * mx[x];
			f[x] = 1; return;
		} 
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		div(l, r, v, lx, m, x<<1), 
		div(l, r, v, m+1, rx, x<<1|1);
		tree[x] = tree[x<<1] + tree[x<<1|1];
		mn[x] = min(mn[x<<1], mn[x<<1|1]);
		mx[x] = max(mx[x<<1], mx[x<<1|1]);
	}
	
	long long get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		return get(l, r, lx, m, x<<1) + get(l, r, m+1, rx, x<<1|1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q, k; cin>>n>>q>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i], tree.sett(i, a[i]);
	while(q--){
		int t; cin>>t;
		if(t == 1){
			int i, v; cin>>i>>v; i--;
			tree.sett(i, v);
		} if(t == 2){
			int l, r; cin>>l>>r; l--, r--;
			tree.div(l, r, k);
		} if(t == 3){
			int l, r; cin>>l>>r; l--, r--;
			cout<<tree.get(l, r)<<"\n";
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75