Submission #50334

#	Time	Username	Problem	Language	Result	Execution time	Memory
50334		top34051	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	311 ms	26368 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,q,k;
int a[maxn];
set<int> pos, del;
long long tree[maxn];
void update(int x, int val) {
	while(x<=n) {
		tree[x] += val;
		x += x&-x;
	}
}
long long query(int x) {
	long long res = 0;
	while(x) {
		res += tree[x];
		x -= x&-x;
	}
	return res;
}
int main() {
	scanf("%d%d%d",&n,&q,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) {
		update(i,a[i]);
		if(a[i]) pos.insert(i);
	}
	while(q--) {
		int type; scanf("%d",&type);
		if(type==1) {
			int x,val; scanf("%d%d",&x,&val);
			update(x, -a[x]);
			a[x] = val;
			update(x, a[x]);
			pos.insert(x);
		}
		else if(type==2) {
			int l,r; scanf("%d%d",&l,&r);
			if(k!=1) {
				del.clear();
				auto it = pos.lower_bound(l);
				while(it!=pos.end() && *it<=r) {
					int x = *it;
					update(x, -a[x]);
					a[x] /= k;
					update(x, a[x]);
					if(a[x]==0) del.insert(x);
					++it;
				}
				for(auto t : del) pos.erase(t);
			}
		}
		else {
			int l,r; scanf("%d%d",&l,&r);
			printf("%lld\n",query(r)-query(l-1));
		}
	}
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&q,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:24:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~
sterilizing.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int type; scanf("%d",&type);
             ~~~~~^~~~~~~~~~~~
sterilizing.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x,val; scanf("%d%d",&x,&val);
               ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int l,r; scanf("%d%d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int l,r; scanf("%d%d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75