oj.uz

Submission #535895

# Submission time Handle Problem Language Result Execution time Memory
535895 2022-03-11T17:33:58 Z oneskovic Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 244 ms 8300 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 && k > 1) // range update
		{
			int l, r; cin >> l >> r;
			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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 4572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 796 KB Output is correct
2 Correct 27 ms 3540 KB Output is correct
3 Correct 26 ms 3540 KB Output is correct
4 Correct 43 ms 2132 KB Output is correct
5 Correct 80 ms 7532 KB Output is correct
6 Correct 77 ms 7520 KB Output is correct
7 Incorrect 82 ms 8300 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4092 KB Output is correct
2 Correct 110 ms 4248 KB Output is correct
3 Correct 110 ms 3612 KB Output is correct
4 Correct 85 ms 2872 KB Output is correct
5 Correct 140 ms 7852 KB Output is correct
6 Correct 170 ms 7608 KB Output is correct
7 Correct 137 ms 7700 KB Output is correct
8 Correct 188 ms 7628 KB Output is correct
9 Correct 173 ms 7936 KB Output is correct
10 Correct 183 ms 7836 KB Output is correct
11 Correct 137 ms 8000 KB Output is correct
12 Correct 244 ms 7764 KB Output is correct