oj.uz

Submission #518887

# Submission time Handle Problem Language Result Execution time Memory
518887 2022-01-25T03:17:54 Z amunduzbaev Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 375 ms 6184 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 7 ms 460 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 4 ms 644 KB Output is correct
7 Correct 5 ms 588 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 7 ms 716 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 6 ms 644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3268 KB Output is correct
2 Correct 44 ms 2400 KB Output is correct
3 Correct 45 ms 4228 KB Output is correct
4 Correct 78 ms 5204 KB Output is correct
5 Correct 64 ms 5316 KB Output is correct
6 Correct 77 ms 5376 KB Output is correct
7 Correct 65 ms 5336 KB Output is correct
8 Correct 70 ms 5316 KB Output is correct
9 Correct 71 ms 5348 KB Output is correct
10 Correct 62 ms 5448 KB Output is correct
11 Correct 67 ms 5420 KB Output is correct
12 Correct 69 ms 5348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 844 KB Output is correct
2 Correct 17 ms 2892 KB Output is correct
3 Correct 21 ms 2948 KB Output is correct
4 Correct 55 ms 1876 KB Output is correct
5 Correct 72 ms 5836 KB Output is correct
6 Correct 67 ms 5892 KB Output is correct
7 Correct 60 ms 4952 KB Output is correct
8 Correct 67 ms 6012 KB Output is correct
9 Correct 62 ms 5964 KB Output is correct
10 Correct 58 ms 6008 KB Output is correct
11 Correct 80 ms 5988 KB Output is correct
12 Correct 63 ms 5964 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3468 KB Output is correct
2 Correct 133 ms 3588 KB Output is correct
3 Correct 163 ms 3084 KB Output is correct
4 Correct 156 ms 2468 KB Output is correct
5 Correct 181 ms 6088 KB Output is correct
6 Correct 245 ms 6132 KB Output is correct
7 Correct 217 ms 6000 KB Output is correct
8 Correct 301 ms 6184 KB Output is correct
9 Correct 239 ms 6136 KB Output is correct
10 Correct 285 ms 6164 KB Output is correct
11 Correct 189 ms 6084 KB Output is correct
12 Correct 375 ms 6132 KB Output is correct