Submission #1275212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275212		reginox	Sterilizing Spray (JOI15_sterilizing)	C++20	10 / 100	57 ms	5416 KiB

sterilizing

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 1e5+3;
const long long up = 1e9+33;
int n, q, k;
int a[N];
ll t[N*4], lz[N*4];

void build(int id, int L, int R){
	if(L == R){
		t[id] = a[L];
		return ;
	}
	lz[id] = 1;
	int mid = (L+R)/2;
	build(id<<1, L, mid); build(id<<1|1, mid+1, R);
	t[id] = t[id<<1] + t[id<<1|1];
}

void down(int id){
	int v = lz[id];
	t[id<<1]/=v;
	t[id<<1|1]/=v;
	lz[id<<1]*=v;
	lz[id<<1|1]*=v;
	lz[id<<1] = min(lz[id<<1], up);
	lz[id<<1|1] = min(lz[id<<1|1], up);
	lz[id] = 1;
}

void update(int id, int l, int r, int u, int v){
	if(u < l || r < u) return ;
	if(l == r){
		t[id] = v;
		lz[id] = 1;
		return ;
	}
	down(id);
	int mid = (l+r)/2;
	update(id<<1, l, mid, u, v); update(id<<1|1, mid+1, r, u, v);
	t[id] = t[id<<1] + t[id<<1|1];
	return ;
}

void spray(int id, int l, int r, int L, int R){
	if(R < l || r < L) return ;
	if(L <= l && r <= R){
		t[id] /= k;
		lz[id] *= k;
		lz[id] = min(lz[id], up);
		return ;
	}
	down(id);
	int mid = (l+r)/2;
	spray(id<<1, l, mid, L, R); spray(id<<1|1, mid+1, r, L, R);
	t[id] = t[id<<1] + t[id<<1|1];
	return ;
}

ll get(int id, int l, int r, int L, int R){
	if(R < l || r < L) return 0;
	if(L <= l && r <= R) return t[id];
	down(id);
	int mid = (l+r)/2;
	return get(id<<1, l, mid, L, R) + get(id<<1|1, mid+1, r, L, R);
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> q >> k;
  for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while(q--){
	int t, l, r; cin >> t >> l >> r;
	if(t == 1) update(1, 1, n, l, r);
	if(t == 2) spray(1, 1, n, l, r);
	if(t == 3) cout << get(1, 1, n, l, r) << "\n";
}
  return 0;
}

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