oj.uz

Submission #553748

# Submission time Handle Problem Language Result Execution time Memory
553748 2022-04-26T19:32:21 Z nafis_shifat Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 157 ms 9084 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
struct BIT
{
	ll bit[mxn] = {};
	void update(int p,ll v) {
		if(p==0) return;
		for(;p<mxn;p+=p&-p) bit[p] += v;
	}
    ll query(int p) {
    	ll r = 0;
    	for(;p>0;p-=p&-p) r += bit[p];
        return r;
    } 
    ll query(int l, int r) {
    	return query(r) - query(l - 1);
    }
} bt;
int a[mxn];
int main() {
	int n, q, k;
	cin >> n >> q >> k;

	set<int> st;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if(a[i] > 0) st.insert(i);

		bt.update(i, a[i]);
	}

	for(int i = 1; i <= q; i++) {
		int tp, l, r;
		scanf("%d%d%d", &tp, &l, &r);

		if(tp == 1) {
			if(a[l] > 0) st.erase(l);

			bt.update(l, r - a[l]);
			a[l] = r;
			if(a[l] > 0) st.insert(l);

		} else if(tp == 2) {
			if(k == 1) continue;
			auto it = st.lower_bound(l);
			while(it != st.end() && *it <= r) {
				int p = *it;
				int lv = a[p];
				a[p] /= k;
				bt.update(p, a[p] - lv);
				if(a[p] == 0) {
					it = st.erase(it);
				} else {
					it++;
				}
			} 
		} else {
			printf("%lld\n", bt.query(l, r));
		}
	}


}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d%d%d", &tp, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 316 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 4 ms 472 KB Output is correct
5 Correct 5 ms 576 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 4 ms 476 KB Output is correct
9 Correct 4 ms 584 KB Output is correct
10 Correct 4 ms 576 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5488 KB Output is correct
2 Correct 48 ms 4212 KB Output is correct
3 Correct 59 ms 6780 KB Output is correct
4 Correct 74 ms 8576 KB Output is correct
5 Correct 80 ms 9068 KB Output is correct
6 Correct 80 ms 9048 KB Output is correct
7 Correct 86 ms 8988 KB Output is correct
8 Correct 84 ms 9084 KB Output is correct
9 Correct 81 ms 8852 KB Output is correct
10 Correct 82 ms 8952 KB Output is correct
11 Correct 77 ms 8892 KB Output is correct
12 Correct 76 ms 8944 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 920 KB Output is correct
2 Correct 15 ms 2132 KB Output is correct
3 Correct 19 ms 2256 KB Output is correct
4 Correct 35 ms 2336 KB Output is correct
5 Correct 54 ms 5224 KB Output is correct
6 Correct 53 ms 5248 KB Output is correct
7 Correct 55 ms 5400 KB Output is correct
8 Correct 51 ms 5196 KB Output is correct
9 Correct 49 ms 5068 KB Output is correct
10 Correct 49 ms 5020 KB Output is correct
11 Correct 50 ms 5056 KB Output is correct
12 Correct 49 ms 5104 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4936 KB Output is correct
2 Correct 63 ms 5268 KB Output is correct
3 Correct 79 ms 4196 KB Output is correct
4 Correct 75 ms 4120 KB Output is correct
5 Correct 103 ms 8832 KB Output is correct
6 Correct 112 ms 8776 KB Output is correct
7 Correct 98 ms 8752 KB Output is correct
8 Correct 127 ms 8864 KB Output is correct
9 Correct 116 ms 8760 KB Output is correct
10 Correct 125 ms 8772 KB Output is correct
11 Correct 101 ms 8764 KB Output is correct
12 Correct 157 ms 8784 KB Output is correct