oj.uz

Submission #264342

# Submission time Handle Problem Language Result Execution time Memory
264342 2020-08-14T06:16:04 Z ruler Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 334 ms 6444 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define endt '\t'
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////
 
const int N = 1e5 + 5;

int n, q, k;
int MX[N << 2];
ll SUM[N << 2];

#define md ((s + e) >> 1)
#define lc (id << 1)
#define rc (lc ^ 1)
void Build(int id = 1, int s = 0, int e = n) {
	if (e - s < 2) {
		int a; cin >> a;
		MX[id] = SUM[id] = a;
		return;
	}
	Build(lc, s, md), Build(rc, md, e);
	SUM[id] = SUM[lc] + SUM[rc];
	MX[id] = max(MX[lc], MX[rc]);
}
void Apply(int l, int r, int id = 1, int s = 0, int e = n) {
	if (l >= e || s >= r || MX[id] == 0 || k == 1) return;
	if (e - s < 2) {
		MX[id] /= k, SUM[id] /= k;
		return;
	}
	Apply(l, r, lc, s, md), Apply(l, r, rc, md, e);
	SUM[id] = SUM[lc] + SUM[rc];
	MX[id] = max(MX[lc], MX[rc]);
}
void Update(int p, int x, int id = 1, int s = 0, int e = n) {
	if (e - s < 2) {
		MX[id] = SUM[id] = x;
		return;
	}
	if (p < md) Update(p, x, lc, s, md);
	else Update(p, x, rc, md, e);
	SUM[id] = SUM[lc] + SUM[rc];
	MX[id] = max(MX[lc], MX[rc]);
}
ll Get(int l, int r, int id = 1, int s = 0, int e = n) {
	if (l >= e || s >= r) return 0;
	if (l <= s && e <= r) return SUM[id];
	return Get(l, r, lc, s, md) + Get(l, r, rc, md, e);
}

int main() {
 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	cin >> n >> q >> k;
	Build();
	while (q--) {
		int t, l, r; cin >> t >> l >> r; l--;
		if (t == 1) Update(l, r);
		else if (t == 2) Apply(l, r);
		else cout << Get(l, r) << endl;
	}

	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2904 KB Output is correct
2 Correct 48 ms 4216 KB Output is correct
3 Correct 44 ms 5368 KB Output is correct
4 Correct 59 ms 5880 KB Output is correct
5 Correct 78 ms 6392 KB Output is correct
6 Correct 66 ms 6392 KB Output is correct
7 Correct 64 ms 6392 KB Output is correct
8 Correct 65 ms 6444 KB Output is correct
9 Correct 63 ms 6392 KB Output is correct
10 Correct 61 ms 6268 KB Output is correct
11 Correct 63 ms 6264 KB Output is correct
12 Correct 62 ms 6264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 512 KB Output is correct
2 Correct 17 ms 1920 KB Output is correct
3 Correct 19 ms 1920 KB Output is correct
4 Correct 52 ms 1152 KB Output is correct
5 Correct 73 ms 3456 KB Output is correct
6 Correct 73 ms 3456 KB Output is correct
7 Correct 79 ms 4216 KB Output is correct
8 Correct 84 ms 4900 KB Output is correct
9 Correct 64 ms 4728 KB Output is correct
10 Correct 66 ms 4728 KB Output is correct
11 Correct 61 ms 4728 KB Output is correct
12 Correct 61 ms 4728 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 2040 KB Output is correct
2 Correct 118 ms 2040 KB Output is correct
3 Correct 138 ms 2040 KB Output is correct
4 Correct 140 ms 1400 KB Output is correct
5 Correct 158 ms 3832 KB Output is correct
6 Correct 182 ms 3708 KB Output is correct
7 Correct 154 ms 3704 KB Output is correct
8 Correct 231 ms 3704 KB Output is correct
9 Correct 219 ms 3832 KB Output is correct
10 Correct 253 ms 3848 KB Output is correct
11 Correct 178 ms 3704 KB Output is correct
12 Correct 334 ms 3836 KB Output is correct