oj.uz

Submission #715884

# Submission time Handle Problem Language Result Execution time Memory
715884 2023-03-28T10:08:52 Z lukameladze Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 216 ms 9572 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,q,k,a[N],tree[N];
set <int> s;
void update(int idx, int val) {
	for (int i = idx; i < N; i+=i&(-i)) {
		tree[i] += val;
	}
}
int getans(int idx) {
	int pas = 0;
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree[i];
	}
	return pas;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q>>k;
	for (int i = 1; i <= n; i++) {
		cin>>a[i];
		if (a[i] > 0) s.insert(i);
		update(i, a[i]);
	}
	while(q--) {
		int ty; 
		cin>>ty;
		if (ty == 1) {
			int idx, val; cin>>idx>>val;
			update(idx, val - a[idx]); a[idx] = val; if (a[idx]) s.insert(idx);			
			continue; 	
		} else if (ty == 2) {
			int l, r; cin>>l>>r;
			if (k == 1) continue;
			vector <int> todel;
			for (auto it = s.lower_bound(l); it != s.end(); it++) {
	
				int id = *it; if (id > r) break; update(id, -a[id]); update(id, a[id] / k); a[id] /= k; if (a[id] == 0) todel.pb(id);
			}
			for (int x : todel) s.erase(s.find(x));
		} else if (ty == 3) {
			int l, r; cin>>l>>r; cout<<getans(r) - getans(l - 1)<<"\n";
		}
	}
}

Compilation message

sterilizing.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 6 ms 516 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 6 ms 600 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 5 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5744 KB Output is correct
2 Correct 41 ms 4408 KB Output is correct
3 Correct 50 ms 7164 KB Output is correct
4 Correct 74 ms 8996 KB Output is correct
5 Correct 73 ms 9528 KB Output is correct
6 Correct 77 ms 9416 KB Output is correct
7 Correct 78 ms 9532 KB Output is correct
8 Correct 80 ms 9420 KB Output is correct
9 Correct 72 ms 9344 KB Output is correct
10 Correct 74 ms 9376 KB Output is correct
11 Correct 77 ms 9332 KB Output is correct
12 Correct 86 ms 9348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1112 KB Output is correct
2 Correct 15 ms 2316 KB Output is correct
3 Correct 18 ms 2632 KB Output is correct
4 Correct 35 ms 2664 KB Output is correct
5 Correct 51 ms 5800 KB Output is correct
6 Correct 53 ms 5784 KB Output is correct
7 Correct 65 ms 6168 KB Output is correct
8 Correct 51 ms 5796 KB Output is correct
9 Correct 50 ms 5692 KB Output is correct
10 Correct 48 ms 5696 KB Output is correct
11 Correct 52 ms 5668 KB Output is correct
12 Correct 54 ms 5692 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 5272 KB Output is correct
2 Correct 77 ms 5520 KB Output is correct
3 Correct 107 ms 4476 KB Output is correct
4 Correct 87 ms 4312 KB Output is correct
5 Correct 126 ms 9444 KB Output is correct
6 Correct 146 ms 9400 KB Output is correct
7 Correct 122 ms 9408 KB Output is correct
8 Correct 198 ms 9572 KB Output is correct
9 Correct 146 ms 9464 KB Output is correct
10 Correct 175 ms 9272 KB Output is correct
11 Correct 127 ms 9276 KB Output is correct
12 Correct 216 ms 9348 KB Output is correct