Submission #50338

#	Time	Username	Problem	Language	Result	Execution time	Memory
50338		gnoor	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	185 ms	7104 KiB

sterilizing

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

map<int,int> st;

long long bit[100100];

void add(int idx,int val) {
	while (idx<100100) {
		bit[idx]+=val;
		idx+=(idx&-idx);
	}
}

long long get(int idx) {
	long long sum=0;
	while (idx) {
		sum+=bit[idx];
		idx-=(idx&-idx);
	}
	return sum;
}

int tbl[100100];

int main () {
	int n,q,k;
	scanf("%d%d%d",&n,&q,&k);
	int x;
	for (int i=1;i<=n;i++) {
		scanf("%d",&x);
		tbl[i]=x;
		//st.insert(make_pair(i,x));
		st[i]=x;
		add(i,x);
	}
	int a,b,c;
	for (int i=0;i<q;i++) {
		scanf("%d%d%d",&a,&b,&c);
		if (k==1) {
			if (a==1) {
				add(b,c-tbl[b]);
				tbl[b]=c;
			} else if (a==3) {
				printf("%lld\n",get(c)-get(b-1));
			}	
			continue;
		}
		if (a==1) {
			//auto &now = st.lower_bound(make_pair(b,-1));
			if (c==0) {
				st.erase(b);
			} else {
				st[b]=c;
			}
		} else if (a==2) {
			//if (k==1) continue;
			auto xx=st.lower_bound(b);
			for(;xx->first<=c&&xx!=st.end();) {
				xx->second/=k;
				if (xx->second==0) {
					auto tmp=xx;
					xx++;
					st.erase(tmp);
				} else {
					xx++;
				}
			}
		} else if (a==3) {
			auto xx=st.lower_bound(b);
			long long ans=0;
			for (;xx->first<=c&&xx!=st.end();xx++) {
				ans+=xx->second;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:32: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:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
sterilizing.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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