oj.uz

Submission #160244

# Submission time Handle Problem Language Result Execution time Memory
160244 2019-10-26T12:25:28 Z iefnah06 Sterilizing Spray (JOI15_sterilizing) C++11
80 / 100
 5000 ms 9692 KB 
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 1.1e5;
int N, Q, K;

ll bit[MAXN];
void update(int i, int v) {
	for (i++; i <= N; i += (i & -i)) {
		bit[i] += v;
	}
}
ll query(int i) {
	ll ans = 0;
	for (; i; i -= (i & -i)) {
		ans += bit[i];
	}
	return ans;
}

map<int, int> vals;
void modify(int i, int v) {
	update(i, -vals[i]);
	vals.erase(i);
	if (v) {
		vals[i] = v;
		update(i, v);
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> Q >> K;
	for (int i = 0; i < N; i++) {
		int v; cin >> v;
		modify(i, v);
	}
	while (Q--) {
		int s, t, u; cin >> s >> t >> u;
		t--;
		if (s == 1) {
			modify(t, u);
		} else if (s == 2) {
			vector<pair<int, int>> cnds;
			{
				auto it = vals.lower_bound(t);
				while (true) {
					if (it == vals.end() || it->first >= u) break;
					cnds.push_back(*it);
					it = next(it);
				}
			}
			for (auto it : cnds) {
				modify(it.first, it.second / K);
			}
		} else {
			cout << query(u) - query(t) << '\n';
		}
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 23 ms 508 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 23 ms 504 KB Output is correct
5 Correct 23 ms 632 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 19 ms 632 KB Output is correct
8 Correct 20 ms 636 KB Output is correct
9 Correct 26 ms 632 KB Output is correct
10 Correct 19 ms 632 KB Output is correct
11 Correct 18 ms 632 KB Output is correct
12 Correct 20 ms 632 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5019 ms 5188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1016 KB Output is correct
2 Correct 32 ms 2040 KB Output is correct
3 Correct 36 ms 2284 KB Output is correct
4 Correct 56 ms 2552 KB Output is correct
5 Correct 108 ms 5112 KB Output is correct
6 Correct 109 ms 5112 KB Output is correct
7 Execution timed out 5027 ms 5060 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 5384 KB Output is correct
2 Correct 378 ms 5388 KB Output is correct
3 Correct 928 ms 4756 KB Output is correct
4 Correct 434 ms 4396 KB Output is correct
5 Correct 771 ms 8920 KB Output is correct
6 Correct 990 ms 9392 KB Output is correct
7 Correct 754 ms 9692 KB Output is correct
8 Correct 1554 ms 9456 KB Output is correct
9 Correct 1198 ms 9012 KB Output is correct
10 Correct 1507 ms 9628 KB Output is correct
11 Correct 901 ms 8844 KB Output is correct
12 Correct 2427 ms 9416 KB Output is correct