oj.uz

Submission #518885

# Submission time Handle Problem Language Result Execution time Memory
518885 2022-01-25T03:15:49 Z amunduzbaev Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 8640 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) return;
		if(lx >= l && rx <= r && (mx[x] / v) == (mn[x] / v)){
			//~ cout<<lx<<" "<<rx<<" "<<mn[x]<<" "<<mx[x]<<"\n";
			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 4 ms 452 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 6 ms 576 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 6 ms 716 KB Output is correct
9 Correct 7 ms 720 KB Output is correct
10 Correct 5 ms 668 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 6 ms 716 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1220 KB Output is correct
2 Correct 18 ms 3208 KB Output is correct
3 Correct 25 ms 3264 KB Output is correct
4 Correct 62 ms 3012 KB Output is correct
5 Correct 100 ms 7244 KB Output is correct
6 Correct 90 ms 7220 KB Output is correct
7 Execution timed out 5078 ms 7400 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 5032 KB Output is correct
2 Correct 145 ms 5128 KB Output is correct
3 Correct 196 ms 4248 KB Output is correct
4 Correct 199 ms 4244 KB Output is correct
5 Correct 215 ms 8572 KB Output is correct
6 Correct 267 ms 8528 KB Output is correct
7 Correct 209 ms 8564 KB Output is correct
8 Correct 334 ms 8628 KB Output is correct
9 Correct 294 ms 8384 KB Output is correct
10 Correct 353 ms 8640 KB Output is correct
11 Correct 245 ms 8356 KB Output is correct
12 Correct 482 ms 8380 KB Output is correct