oj.uz

Submission #535897

# Submission time Handle Problem Language Result Execution time Memory
535897 2022-03-11T17:35:12 Z oneskovic Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 245 ms 8916 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

class SegmentTree
{
public:
	SegmentTree(const vector<ll>& elements);
	ll sum_query(int l, int r);
	void update(int pos, ll new_value);
private:
	vector<ll> tree;
	int element_cnt;
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, query_cnt, k; cin >> n >> query_cnt >> k;
	vector<ll> elements(n);
	set<int> nonzero_positions;
	for (int i = 0; i < n; i++)
	{
		cin >> elements[i];
		nonzero_positions.insert(i);
	}
	auto tree = SegmentTree(elements);
	
	for (int query_no = 0; query_no < query_cnt; query_no++)
	{
		int type; cin >> type;
		if (type == 1) // point update
		{
			int pos; cin >> pos;
			pos--;
			ll new_val; cin >> new_val;
			nonzero_positions.insert(pos);
			tree.update(pos, new_val);
			elements[pos] = new_val;
		}
		else if (type == 2) // range update
		{
			int l, r; cin >> l >> r;
			if (k == 1)
				continue;
			
			l--; r--;
			auto it = nonzero_positions.lower_bound(l);
			vector<int> zero_positions;
			while (it != nonzero_positions.end() && * it <= r)
			{
				int i = *it;
				elements[i] /= k;
				if (elements[i] == 0)
					zero_positions.push_back(i);
				tree.update(i, elements[i]);
				it++;
			}
			for (int i: zero_positions)
				nonzero_positions.erase(i);
		}
		else // range query
		{
			int l, r; cin >> l >> r;
			l--;
			ll sum = tree.sum_query(l, r);
			cout << sum << "\n";
		}
	}

	return 0;
}

SegmentTree::SegmentTree(const vector<ll>& elements)
{
	element_cnt = elements.size();
	tree = vector<ll>(2 * element_cnt);
	copy(elements.begin(), elements.end(), tree.begin() + element_cnt);
	for (int i = element_cnt - 1; i > 0; i--)
		tree[i] = tree[2 * i] + tree[2 * i + 1];
}

ll SegmentTree::sum_query(int l, int r)
{
	l += element_cnt;
	r += element_cnt;
	ll sum = 0;
	while (l < r)
	{
		if (l % 2 == 1)
			sum += tree[l++];
		if (r % 2 == 1)
			sum += tree[--r];
		l /= 2;
		r /= 2;
	}
	return sum;
}

void SegmentTree::update(int pos, ll new_value)
{
	pos += element_cnt;
	tree[pos] = new_value;
	for (int i = pos / 2; i > 0; i /= 2)
		tree[i] = tree[2 * i] + tree[2 * i + 1];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 4152 KB Output is correct
2 Correct 43 ms 2960 KB Output is correct
3 Correct 48 ms 6052 KB Output is correct
4 Correct 74 ms 7644 KB Output is correct
5 Correct 76 ms 7784 KB Output is correct
6 Correct 79 ms 7852 KB Output is correct
7 Correct 74 ms 7776 KB Output is correct
8 Correct 77 ms 7732 KB Output is correct
9 Correct 78 ms 7792 KB Output is correct
10 Correct 76 ms 7756 KB Output is correct
11 Correct 73 ms 7756 KB Output is correct
12 Correct 72 ms 7804 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 792 KB Output is correct
2 Correct 22 ms 3540 KB Output is correct
3 Correct 26 ms 3540 KB Output is correct
4 Correct 43 ms 2184 KB Output is correct
5 Correct 84 ms 7528 KB Output is correct
6 Correct 78 ms 7420 KB Output is correct
7 Correct 74 ms 7464 KB Output is correct
8 Correct 80 ms 8916 KB Output is correct
9 Correct 75 ms 8800 KB Output is correct
10 Correct 71 ms 8728 KB Output is correct
11 Correct 71 ms 8832 KB Output is correct
12 Correct 70 ms 8716 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 4072 KB Output is correct
2 Correct 80 ms 4192 KB Output is correct
3 Correct 108 ms 3612 KB Output is correct
4 Correct 85 ms 2800 KB Output is correct
5 Correct 136 ms 7640 KB Output is correct
6 Correct 155 ms 7624 KB Output is correct
7 Correct 131 ms 7628 KB Output is correct
8 Correct 184 ms 7696 KB Output is correct
9 Correct 160 ms 7920 KB Output is correct
10 Correct 181 ms 7796 KB Output is correct
11 Correct 136 ms 7916 KB Output is correct
12 Correct 245 ms 7768 KB Output is correct