oj.uz

Submission #264337

# Submission time Handle Problem Language Result Execution time Memory
264337 2020-08-14T06:15:03 Z ruler Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 6216 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) 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 3 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 5 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 4 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1024 KB Output is correct
2 Correct 16 ms 2176 KB Output is correct
3 Correct 19 ms 2432 KB Output is correct
4 Correct 56 ms 2368 KB Output is correct
5 Correct 64 ms 4984 KB Output is correct
6 Correct 66 ms 4984 KB Output is correct
7 Execution timed out 5044 ms 4448 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3604 KB Output is correct
2 Correct 119 ms 3832 KB Output is correct
3 Correct 132 ms 3196 KB Output is correct
4 Correct 140 ms 3064 KB Output is correct
5 Correct 169 ms 6216 KB Output is correct
6 Correct 193 ms 6136 KB Output is correct
7 Correct 166 ms 6180 KB Output is correct
8 Correct 260 ms 6156 KB Output is correct
9 Correct 216 ms 6008 KB Output is correct
10 Correct 255 ms 6008 KB Output is correct
11 Correct 186 ms 6008 KB Output is correct
12 Correct 352 ms 6156 KB Output is correct