oj.uz

Submission #969659

# Submission time Handle Problem Language Result Execution time Memory
969659 2024-04-25T12:36:39 Z starchan Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 172 ms 10576 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

struct segment_tree
{
	vector<int> tree, mx;
	int K, N;
	void init(int n)
	{
		N = n;
		tree.resize(4*n+5);
		mx.resize(4*n+5);
		return;
	}
	void build(const vector<int> &v, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l == r)
		{
			tree[id] = v[m];
			mx[id] = v[m];
			return;
		}
		build(v, 2*id, l, m);
		build(v, 2*id+1, m+1, r);
		tree[id] = tree[2*id]+tree[2*id+1];
		mx[id] = max(mx[2*id], mx[2*id+1]);
		return;
	}
	void cringe(int ql, int qr, int id, int l, int r)
	{
		if(K == 1)
			return;
		if(qr < l || r < ql)
			return;
		if(l == r)
		{
			tree[id]/=K;
			mx[id]/=K;
			return;
		}
		int m = (l+r)/2;
		if(mx[2*id])
			cringe(ql, qr, 2*id, l, m);
		if(mx[2*id+1])
			cringe(ql, qr, 2*id+1, m+1, r);
		tree[id] = tree[2*id]+tree[2*id+1];
		mx[id] = max(mx[2*id], mx[2*id+1]);
		return;
	}
	void upd(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return;
		if(ql <= l && r <= qr)
		{
			if(mx[id])
				cringe(ql, qr, id, l, r);
			return;
		}
		int m = (l+r)/2;
		upd(ql, qr, 2*id, l, m);
		upd(ql, qr, 2*id+1, m+1, r);
		tree[id] = tree[2*id]+tree[2*id+1];
		mx[id] = max(mx[2*id], mx[2*id+1]);
		return;
	}
	void pnt(int p, int Val, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = Val;
			mx[id] = Val;
			return;
		}
		int m = (l+r)/2;
		if(p <= m)
			pnt(p, Val, 2*id, l, m);
		else
			pnt(p, Val, 2*id+1, m+1, r);
		tree[id] = tree[2*id]+tree[2*id+1];
		mx[id] = max(mx[2*id], mx[2*id+1]);
		return;
	}
	int query(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return 0;
		if(ql <= l && r <= qr)
			return tree[id];
		int m = (l+r)/2;
		int s1 = query(ql, qr, 2*id, l, m);
		int s2 = query(ql, qr, 2*id+1, m+1, r);
		return s1+s2;	
	}
};


signed main()
{
	fast();
	segment_tree work;
	int n, q;
	cin >> n >> q >> work.K;
	vector<int> a(n+1);
	work.init(n);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	work.build(a, 1, 1, n);
	while(q--)
	{
		int typ, x, y; cin >> typ >> x >> y;
		if(typ == 1)
			work.pnt(x, y, 1, 1, n);
		else if(typ == 2)
			work.upd(x, y, 1, 1, n);
		else if(typ == 3)
			cout << work.query(x, y, 1, 1, n) << "\n";
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 740 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6228 KB Output is correct
2 Correct 43 ms 4632 KB Output is correct
3 Correct 43 ms 7772 KB Output is correct
4 Correct 49 ms 9660 KB Output is correct
5 Correct 56 ms 10576 KB Output is correct
6 Correct 57 ms 10204 KB Output is correct
7 Correct 58 ms 10244 KB Output is correct
8 Correct 56 ms 10324 KB Output is correct
9 Correct 55 ms 10064 KB Output is correct
10 Correct 52 ms 10064 KB Output is correct
11 Correct 52 ms 10196 KB Output is correct
12 Correct 51 ms 10100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1368 KB Output is correct
2 Correct 11 ms 3676 KB Output is correct
3 Correct 15 ms 3932 KB Output is correct
4 Correct 44 ms 3236 KB Output is correct
5 Correct 58 ms 9140 KB Output is correct
6 Correct 55 ms 8788 KB Output is correct
7 Correct 53 ms 9044 KB Output is correct
8 Correct 54 ms 8920 KB Output is correct
9 Correct 50 ms 8788 KB Output is correct
10 Correct 49 ms 8788 KB Output is correct
11 Correct 57 ms 8628 KB Output is correct
12 Correct 55 ms 8696 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5724 KB Output is correct
2 Correct 70 ms 5968 KB Output is correct
3 Correct 79 ms 4904 KB Output is correct
4 Correct 86 ms 4688 KB Output is correct
5 Correct 101 ms 10056 KB Output is correct
6 Correct 112 ms 10068 KB Output is correct
7 Correct 104 ms 10208 KB Output is correct
8 Correct 138 ms 10068 KB Output is correct
9 Correct 118 ms 9920 KB Output is correct
10 Correct 151 ms 10068 KB Output is correct
11 Correct 102 ms 10068 KB Output is correct
12 Correct 172 ms 10124 KB Output is correct