Submission #1128852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128852		Alihan_8	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	270 ms	6952 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

#define L(x) x << 1
#define R(x) x << 1 | 1
#define int long long

const int N = 1e5 + 5;

int n, k;

int sm[N * 4], lazy[N * 4], mx[N * 4];

void push(int v, int l, int r){
	if ( !lazy[v] ) return;
	
	if ( l != r ) lazy[L(v)] = lazy[R(v)] = 1;
	
	mx[v] = sm[v] = 0;
	lazy[v] = 0;
}

void pull(int v, int l, int r){
	int m = (l + r) / 2;
	
	push(L(v), l, m), push(R(v), m + 1, r);
	
	sm[v] = sm[L(v)] + sm[R(v)];
	mx[v] = max(mx[L(v)], mx[R(v)]);
}

void modify(int v, int l, int r){
	push(v, l, r);
	
	if ( mx[v] < k ){
		lazy[v] = 1;
		push(v, l, r);
		return;
	}
	
	if ( l == r ){
		sm[v] /= k; mx[v] /= k;
		return;
	}
	
	int m = (l + r) / 2;
	
	modify(L(v), l, m);	
	modify(R(v), m + 1, r);
	
	pull(v, l, r);
}

void upd(int v, int l, int r, int tl, int tr){
	push(v, l, r);
	
	if ( l > tr or r < tl ) return;
	
	if ( tl <= l && tr >= r ){
		modify(v, l, r);
		return;
	}
	
	int m = (l + r) / 2;
	
	upd(L(v), l, m, tl, tr);
	upd(R(v), m + 1, r, tl, tr);
	
	pull(v, l, r);
}

void set_(int v, int l, int r, int p, int x){
	push(v, l, r);
	
	if ( l == r ){
		sm[v] = mx[v] = x;	
		return;
	}
	
	int m = (l + r) / 2;
	
	if ( p <= m ) set_(L(v), l, m, p, x);
	else set_(R(v), m + 1, r, p, x);
	
	pull(v, l, r);
}

int get(int v, int l, int r, int tl, int tr){
	push(v, l, r);
	
	if ( l > tr or r < tl ) return 0;
	
	if ( tl <= l && tr >= r ) return sm[v];
	
	int m = (l + r) / 2;
	
	return get(L(v), l, m, tl, tr) + get(R(v), m + 1, r, tl, tr);
}

struct Fenw{
	vector <int> fenw;
	
	int n;
	
	Fenw(int n) : fenw(n + 1, 0), n(n) {}
	
	void upd(int i, int v){
		for (; i <= n; i += i & -i ) fenw[i] += v;
	}
	
	int get(int i){
		int cnt = 0;
		
		for (; i > 0; i -= i & -i ) cnt += fenw[i];
		
		return cnt;
	}
	
	int get(int l, int r){ return get(r) - get(l - 1); }
}; 

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int q; cin >> n >> q >> k;
	
	if ( k == 1 ){ 
		vector <int> c(n + 1);
		
		Fenw fn(n);
		
		for ( int i = 1; i <= n; i++ ){
			cin >> c[i];
			
			fn.upd(i, c[i]);
		}
		
		while ( q-- ){
			int t, l, r; cin >> t >> l >> r;
			
			if ( t == 1 ){
				fn.upd(l, -c[l]);
				swap(c[l], r);
				fn.upd(l, c[l]);
			} else if ( t == 3 ){
				cout << fn.get(l, r) << '\n';
			}
		} exit(0);
	}
	
	for ( int i = 1; i <= n; i++ ){
		int x; cin >> x;
		
		set_(1, 1, n, i, x);
	}
	
	while ( q-- ){
		int t, l, r; cin >> t >> l >> r;
		
		if ( t == 1 ){
			set_(1, 1, n, l, r);
		} else if ( t == 2 ){
			upd(1, 1, n, l, r);
		} else{
			cout << get(1, 1, n, l, r) << '\n';
		}
	}
}

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