oj.uz

Submission #915118

# Submission time Handle Problem Language Result Execution time Memory
915118 2024-01-23T11:20:10 Z penguin133 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 270 ms 10484 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q,k;
int A[200005], ft[200005];
set<int>s;
set<int> :: iterator it;
void update(int x, int v){
	for(;x<=n;x += (x & (-x)))ft[x] += v;
}
int query(int p){
	int sum = 0;
	for(;p;p -= (p & (-p)))sum += ft[p];
	return sum;
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q >> k;
	for(int i=1;i<=n;i++){
		cin >> A[i];
		update(i, A[i]);
		if(A[i])s.insert(i);	
	}
	while(q--){
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 2){
			if(k == 1)continue;
			vector<int>v;
			for(it = s.begin(); it != s.end();it++){
				int x = *it;
				if(b <= x && x <= c){
					update(x, -A[x]);
					update(x, A[x]/k);
					A[x] /= k;
					if(!A[x])v.push_back(x);
				}
			}
			for(int i=0;i<v.size();i++)s.erase(v[i]);
		}
		else if(a == 1){
			update(b,-A[b]);
			update(b,c);
			A[b] = c;
			if(A[b])s.insert(b);	
		}
		else cout << query(c) - query(b-1) << '\n';
	}
}

Compilation message

sterilizing.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:39:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int i=0;i<v.size();i++)s.erase(v[i]);
      |                ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 5 ms 2652 KB Output is correct
8 Correct 5 ms 2652 KB Output is correct
9 Correct 6 ms 2648 KB Output is correct
10 Correct 5 ms 2652 KB Output is correct
11 Correct 6 ms 2532 KB Output is correct
12 Correct 5 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7252 KB Output is correct
2 Correct 33 ms 6224 KB Output is correct
3 Correct 36 ms 8020 KB Output is correct
4 Correct 58 ms 9756 KB Output is correct
5 Correct 58 ms 10340 KB Output is correct
6 Correct 61 ms 10248 KB Output is correct
7 Correct 55 ms 10268 KB Output is correct
8 Correct 54 ms 10300 KB Output is correct
9 Correct 62 ms 10148 KB Output is correct
10 Correct 53 ms 10276 KB Output is correct
11 Correct 51 ms 10276 KB Output is correct
12 Correct 52 ms 10196 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3160 KB Output is correct
2 Correct 13 ms 4024 KB Output is correct
3 Correct 16 ms 4188 KB Output is correct
4 Correct 28 ms 4520 KB Output is correct
5 Correct 53 ms 7124 KB Output is correct
6 Correct 45 ms 6736 KB Output is correct
7 Correct 36 ms 6992 KB Output is correct
8 Correct 45 ms 6712 KB Output is correct
9 Correct 37 ms 6464 KB Output is correct
10 Correct 42 ms 6468 KB Output is correct
11 Correct 37 ms 6476 KB Output is correct
12 Correct 37 ms 6464 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 6724 KB Output is correct
2 Correct 96 ms 6932 KB Output is correct
3 Correct 169 ms 5996 KB Output is correct
4 Correct 108 ms 5996 KB Output is correct
5 Correct 171 ms 10292 KB Output is correct
6 Correct 202 ms 10068 KB Output is correct
7 Correct 149 ms 10324 KB Output is correct
8 Correct 270 ms 10484 KB Output is correct
9 Correct 104 ms 10192 KB Output is correct
10 Correct 111 ms 10100 KB Output is correct
11 Correct 87 ms 10048 KB Output is correct
12 Correct 136 ms 10008 KB Output is correct