Submission #264337

#	Time	Username	Problem	Language	Result	Execution time	Memory
264337		ruler	Sterilizing Spray (JOI15_sterilizing)	C++14	80 / 100	5102 ms	6216 KiB

sterilizing

// 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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75