oj.uz

Submission #160245

# Submission time Handle Problem Language Result Execution time Memory
160245 2019-10-26T12:27:00 Z iefnah06 Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 2316 ms 8884 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) {
			if (K == 1) continue;
			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 3 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 23 ms 504 KB Output is correct
5 Correct 22 ms 504 KB Output is correct
6 Correct 15 ms 504 KB Output is correct
7 Correct 21 ms 644 KB Output is correct
8 Correct 20 ms 504 KB Output is correct
9 Correct 26 ms 504 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 19 ms 632 KB Output is correct
12 Correct 20 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4600 KB Output is correct
2 Correct 82 ms 4184 KB Output is correct
3 Correct 109 ms 6520 KB Output is correct
4 Correct 158 ms 8368 KB Output is correct
5 Correct 165 ms 8796 KB Output is correct
6 Correct 165 ms 8796 KB Output is correct
7 Correct 166 ms 8696 KB Output is correct
8 Correct 287 ms 8884 KB Output is correct
9 Correct 176 ms 8684 KB Output is correct
10 Correct 163 ms 8568 KB Output is correct
11 Correct 160 ms 8792 KB Output is correct
12 Correct 163 ms 8668 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 632 KB Output is correct
2 Correct 32 ms 1904 KB Output is correct
3 Correct 37 ms 2040 KB Output is correct
4 Correct 54 ms 1272 KB Output is correct
5 Correct 107 ms 3704 KB Output is correct
6 Correct 111 ms 3704 KB Output is correct
7 Correct 122 ms 4760 KB Output is correct
8 Correct 111 ms 4432 KB Output is correct
9 Correct 109 ms 4496 KB Output is correct
10 Correct 149 ms 5012 KB Output is correct
11 Correct 104 ms 4472 KB Output is correct
12 Correct 105 ms 4916 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 4000 KB Output is correct
2 Correct 373 ms 3848 KB Output is correct
3 Correct 829 ms 3648 KB Output is correct
4 Correct 422 ms 2752 KB Output is correct
5 Correct 751 ms 6780 KB Output is correct
6 Correct 999 ms 6988 KB Output is correct
7 Correct 735 ms 7512 KB Output is correct
8 Correct 1422 ms 7692 KB Output is correct
9 Correct 1201 ms 7876 KB Output is correct
10 Correct 1504 ms 7880 KB Output is correct
11 Correct 901 ms 7940 KB Output is correct
12 Correct 2316 ms 7892 KB Output is correct