Submission #1289685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289685		am_aadvik	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	375 ms	121764 KiB

sterilizing

#include <iostream>
#include <vector>
#define int long long
using namespace std;

class segtree {
private:
	vector<vector<int>> st;
	vector<int> lazy, a;
	int k;
	const int dv = 0, ldv = 0;
	vector<int> join(vector<int>& l, vector<int>& r) {
		vector<int> x(l.size());
		for (int i = 0; i < l.size(); ++i)
			x[i] = l[i] + r[i];
		return x;
	}
	int ljoin(int l, int r) {
		return l + r;
	}
	void upd(int s, int e, int node, int val) {
		if (val == ldv) return;
		if (val > 32)
			for (int i = 0; i < 33; ++i)
				st[node][i] = 0;
		else
			for (int i = 0; i < 33; ++i)
				if ((i + val) >= 33) st[node][i] = 0;
				else st[node][i] = st[node][i + val];
	}
	vector<int> build(int s, int e, int node) {
		if (s == e) {
			int cur = a[s];
			for (int i = 0; i < 33; ++i)
				st[node][i] = cur, cur /= k;
			return st[node];
		}
		int mid = (s + e) / 2;
		auto l = build(s, mid, node * 2);
		auto r = build(mid + 1, e, node * 2 + 1);
		return st[node] = join(l, r);
	}
	void update(int s, int e, int node, int l, int r, int val) {
		if ((l > e) || (r < s)) return;
		if ((l <= s) && (r >= e)) {
			upd(s, e, node, val);
			lazy[node] = ljoin(lazy[node], val);
			return;
		}
		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;
		update(s, mid, node * 2, l, r, val);
		update(mid + 1, e, node * 2 + 1, l, r, val);
		st[node] = join(st[node * 2], st[node * 2 + 1]);
	}
	void update2(int s, int e, int node, int i, int val) {
		if ((i > e) || (i < s)) return;
		if (s == e) {
			int cur = val;
			for (int i = 0; i < 33; ++i)
				st[node][i] = cur, cur /= k;
			return;
		}
		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;
		update2(s, mid, node * 2, i, val);
		update2(mid + 1, e, node * 2 + 1, i, val);
		st[node] = join(st[node * 2], st[node * 2 + 1]);
	}
	int query(int s, int e, int node, int l, int r) {
		if ((l > e) || (r < s)) return dv;
		if ((l <= s) && (r >= e)) return st[node][0];

		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;
		return ljoin(query(s, mid, node * 2, l, r),
			query(mid + 1, e, node * 2 + 1, l, r));
	}
public:
	segtree(int n, vector<int> arr, int K) {
		a = arr; k = K;
		st.resize(4 * n, vector<int>(33, dv));
		lazy.resize(4 * n, ldv);
		build(0, n - 1, 1);
	}
	int query(int l, int r) {
		return query(0, a.size() - 1, 1, l, r);
	}
	void update(int l, int r, int val) {
		update(0, a.size() - 1, 1, l, r, val);
	}
	void update2(int i, int val) {
		update2(0, a.size() - 1, 1, i, val);
	}
};
int32_t main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, k, q; cin >> n >> q >> k;
	vector<int> a(n);
	for (auto& x : a) cin >> x;
	segtree s(n, a, k);
	while (q--) {
		int t, l, r; cin >> t >> l >> r;
		if (t == 1)
			s.update2(l - 1, r);
		else if (t == 2) {
			if (k != 1)
				s.update(l - 1, r - 1, 1);
		}
		else
			cout << s.query(l - 1, r - 1) << endl;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75