oj.uz

Submission #518886

# Submission time Handle Problem Language Result Execution time Memory
518886 2022-01-25T03:17:05 Z amunduzbaev Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 526 ms 7752 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) 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 1 ms 460 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 6 ms 588 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 6 ms 644 KB Output is correct
8 Correct 5 ms 588 KB Output is correct
9 Correct 7 ms 588 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 8 ms 588 KB Output is correct
12 Correct 6 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3828 KB Output is correct
2 Correct 58 ms 3932 KB Output is correct
3 Correct 47 ms 5832 KB Output is correct
4 Correct 58 ms 7228 KB Output is correct
5 Correct 92 ms 7752 KB Output is correct
6 Correct 71 ms 7712 KB Output is correct
7 Correct 67 ms 7752 KB Output is correct
8 Correct 71 ms 7640 KB Output is correct
9 Correct 66 ms 7520 KB Output is correct
10 Correct 62 ms 7612 KB Output is correct
11 Correct 73 ms 7564 KB Output is correct
12 Correct 65 ms 7620 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 840 KB Output is correct
2 Correct 30 ms 2852 KB Output is correct
3 Correct 39 ms 2936 KB Output is correct
4 Correct 69 ms 1824 KB Output is correct
5 Correct 87 ms 5908 KB Output is correct
6 Correct 95 ms 5876 KB Output is correct
7 Correct 62 ms 4936 KB Output is correct
8 Correct 112 ms 7412 KB Output is correct
9 Correct 83 ms 7144 KB Output is correct
10 Correct 95 ms 7108 KB Output is correct
11 Correct 90 ms 7136 KB Output is correct
12 Correct 82 ms 7184 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 3476 KB Output is correct
2 Correct 150 ms 3460 KB Output is correct
3 Correct 208 ms 3104 KB Output is correct
4 Correct 201 ms 2444 KB Output is correct
5 Correct 250 ms 6052 KB Output is correct
6 Correct 264 ms 6124 KB Output is correct
7 Correct 216 ms 6084 KB Output is correct
8 Correct 325 ms 6196 KB Output is correct
9 Correct 316 ms 6128 KB Output is correct
10 Correct 358 ms 6080 KB Output is correct
11 Correct 256 ms 6108 KB Output is correct
12 Correct 526 ms 6148 KB Output is correct