Submission #553748

#	Time	Username	Problem	Language	Result	Execution time	Memory
553748		nafis_shifat	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	157 ms	9084 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75