oj.uz

답안 #535893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535893 2022-03-11T17:31:50 Z oneskovic Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 10180 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;
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5091 ms 3880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1108 KB Output is correct
2 Correct 24 ms 3796 KB Output is correct
3 Correct 26 ms 3976 KB Output is correct
4 Correct 43 ms 3288 KB Output is correct
5 Correct 81 ms 8884 KB Output is correct
6 Correct 80 ms 8984 KB Output is correct
7 Execution timed out 5064 ms 8400 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 4108 KB Output is correct
2 Correct 79 ms 4140 KB Output is correct
3 Correct 113 ms 4744 KB Output is correct
4 Correct 87 ms 4556 KB Output is correct
5 Correct 137 ms 10148 KB Output is correct
6 Correct 152 ms 10180 KB Output is correct
7 Correct 137 ms 10088 KB Output is correct
8 Correct 189 ms 10172 KB Output is correct
9 Correct 164 ms 10064 KB Output is correct
10 Correct 179 ms 10172 KB Output is correct
11 Correct 138 ms 10008 KB Output is correct
12 Correct 240 ms 10076 KB Output is correct