oj.uz

Submission #380519

# Submission time Handle Problem Language Result Execution time Memory
380519 2021-03-22T06:47:57 Z pure_mem Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 337 ms 7404 KB 
#include <bits/stdc++.h>
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int N = 1e5 + 12;
const ll INF = 1e18;

ll t1[N * 4], t2[N * 4]; 
int n, q, k;
void build(int v, int tl, int tr){
	if(tl == tr){
		cin >> t1[v], t2[v] = t1[v];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm), build(v * 2 + 1, tm + 1, tr);
	t1[v] = t1[v * 2] + t1[v * 2 + 1];
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
void upd(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		if(tl == tr){
			t1[v] /= k, t2[v] = t1[v];
			return;
		}
		else if(t2[v] == 0){
			return;
		}
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r);
	upd(v * 2 + 1, tm + 1, tr, l, r);
	t1[v] = t1[v * 2] + t1[v * 2 + 1];
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
void upd1(int v, int tl, int tr, int pos){
	if(tl == tr){
		cin >> t1[v], t2[v] = t1[v];
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)
		upd1(v * 2, tl, tm, pos);
	else
		upd1(v * 2 + 1, tm + 1, tr, pos);
	t1[v] = t1[v * 2] + t1[v * 2 + 1];
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
ll get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return t1[v];
	int tm = (tl + tr) / 2;
	return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q >> k, build(1, 1, n);
	for(int tc, l, r;q--;){
		cin >> tc >> l;
		if(tc == 1){
			upd1(1, 1, n, l);
		}	
		else if(tc == 2){
			cin >> r;
			if(k > 1)
				upd(1, 1, n, l, r);
		}
		else{
			cin >> r, cout << get(1, 1, n, l, r) << "\n";
		}
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4844 KB Output is correct
2 Correct 49 ms 4460 KB Output is correct
3 Correct 46 ms 6380 KB Output is correct
4 Correct 63 ms 7020 KB Output is correct
5 Correct 75 ms 7404 KB Output is correct
6 Correct 71 ms 7404 KB Output is correct
7 Correct 71 ms 7404 KB Output is correct
8 Correct 75 ms 7404 KB Output is correct
9 Correct 68 ms 7276 KB Output is correct
10 Correct 66 ms 7276 KB Output is correct
11 Correct 66 ms 7236 KB Output is correct
12 Correct 67 ms 7276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1132 KB Output is correct
2 Correct 17 ms 2668 KB Output is correct
3 Correct 22 ms 2796 KB Output is correct
4 Correct 66 ms 2688 KB Output is correct
5 Correct 90 ms 5996 KB Output is correct
6 Correct 89 ms 5996 KB Output is correct
7 Correct 62 ms 6124 KB Output is correct
8 Correct 88 ms 5996 KB Output is correct
9 Correct 78 ms 5868 KB Output is correct
10 Correct 78 ms 5868 KB Output is correct
11 Correct 78 ms 5868 KB Output is correct
12 Correct 78 ms 5868 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 4204 KB Output is correct
2 Correct 120 ms 4364 KB Output is correct
3 Correct 142 ms 3820 KB Output is correct
4 Correct 154 ms 3308 KB Output is correct
5 Correct 176 ms 7148 KB Output is correct
6 Correct 203 ms 7148 KB Output is correct
7 Correct 177 ms 7276 KB Output is correct
8 Correct 240 ms 7276 KB Output is correct
9 Correct 217 ms 7148 KB Output is correct
10 Correct 246 ms 7148 KB Output is correct
11 Correct 182 ms 7148 KB Output is correct
12 Correct 337 ms 7144 KB Output is correct