oj.uz

Submission #94644

# Submission time Handle Problem Language Result Execution time Memory
94644 2019-01-22T04:52:46 Z shoemakerjo Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 606 ms 10508 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int maxn = 100010;

set<int> nonz; //nonzero

int N, Q, K;
int nums[maxn];
ll seg[maxn*4];

ll query(int qs, int qe, int ss = 1, int se = N, int si = 0) {
	if (qs > qe || ss > se || qs > se || qe < ss) return 0LL;
	if (qs <= ss && se <= qe) return seg[si];
	int mid = (ss+se)/2;
	return query(qs, qe, ss, mid, si*2+1) + 
		query(qs, qe, mid+1, se, si*2+2);

}

void update(int spot, ll val, int ss = 1, int se = N, int si = 0) {
	if (ss == se) {
		seg[si] = val;
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) update(spot, val, ss, mid, si*2+1);
	else update(spot, val, mid+1, se, si*2+2);
	seg[si] = seg[si*2+1] + seg[si*2+2];
}	

void buildtree(int ss = 1, int se = N, int si = 0) {
	if (ss == se) {
		seg[si] = nums[ss];
		return;
	}
	int mid = (ss+se)/2;
	buildtree(ss, mid, si*2+1);
	buildtree(mid+1, se, si*2+2);
	seg[si] = seg[si*2+1] + seg[si*2+2];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> Q >> K;
	for (int i = 1; i <= N; i++) {
		cin >> nums[i];
		if (nums[i]) nonz.insert(i);
	}
	buildtree();
	int tp, a, b;	
	while (Q--) {
		cin >> tp >> a >> b;
		if (tp == 1) {
			update(a, b);
			nums[a] = b;
			if (nums[a]) {
				nonz.insert(a);
			}
		}
		else if (tp == 2) {
			//this is the big one
			if (K == 1) continue;
			auto it = nonz.lower_bound(a);
			while (it != nonz.end() && *it <= b) {
				int cur = *it;
				nums[cur] = nums[cur]/K;

				// cout <<  cur << " changed to " << nums[cur] << endl;

				update(cur, nums[cur]);
				if (nums[cur] == 0) {
					it = nonz.erase(it);
				}
				else {
					++it;
				}
			}
		}
		else {
			cout << query(a, b) << '\n';
		}
	}
	cout.flush();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 10 ms 636 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 9 ms 632 KB Output is correct
8 Correct 9 ms 632 KB Output is correct
9 Correct 10 ms 632 KB Output is correct
10 Correct 8 ms 632 KB Output is correct
11 Correct 8 ms 632 KB Output is correct
12 Correct 8 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6264 KB Output is correct
2 Correct 63 ms 5112 KB Output is correct
3 Correct 75 ms 8312 KB Output is correct
4 Correct 109 ms 10076 KB Output is correct
5 Correct 106 ms 10488 KB Output is correct
6 Correct 105 ms 10456 KB Output is correct
7 Correct 112 ms 10436 KB Output is correct
8 Correct 121 ms 10508 KB Output is correct
9 Correct 105 ms 10360 KB Output is correct
10 Correct 110 ms 10360 KB Output is correct
11 Correct 102 ms 10360 KB Output is correct
12 Correct 97 ms 10328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1144 KB Output is correct
2 Correct 19 ms 2936 KB Output is correct
3 Correct 24 ms 3016 KB Output is correct
4 Correct 51 ms 2808 KB Output is correct
5 Correct 80 ms 6648 KB Output is correct
6 Correct 79 ms 6776 KB Output is correct
7 Correct 80 ms 7036 KB Output is correct
8 Correct 83 ms 6776 KB Output is correct
9 Correct 73 ms 6520 KB Output is correct
10 Correct 73 ms 6552 KB Output is correct
11 Correct 75 ms 6520 KB Output is correct
12 Correct 75 ms 6520 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 5752 KB Output is correct
2 Correct 153 ms 5952 KB Output is correct
3 Correct 252 ms 4984 KB Output is correct
4 Correct 169 ms 4472 KB Output is correct
5 Correct 264 ms 10296 KB Output is correct
6 Correct 315 ms 10360 KB Output is correct
7 Correct 250 ms 10352 KB Output is correct
8 Correct 422 ms 10340 KB Output is correct
9 Correct 342 ms 10232 KB Output is correct
10 Correct 420 ms 10252 KB Output is correct
11 Correct 268 ms 10112 KB Output is correct
12 Correct 606 ms 10104 KB Output is correct