Submission #25109

#	Time	Username	Problem	Language	Result	Execution time	Memory
25109		kdh9949	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	4166 ms	2456 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 100000, B = 41;
int n, q, K;

struct Buc{
	int a[B], c, nc;
	ll s;
	void ch(int x, int v){ s -= a[x]; a[x] = v; s += a[x]; }
	void dv(int x){ s -= a[x]; a[x] /= K; s += a[x]; }
	void rs(){
		s = 0;
		for(int i = 0; i < B; i++) s += a[i];
	}
	ll rec(){
		while(c <= 30 && c < nc){
			for(int i = 0; i < B; i++) a[i] /= K;
			c++;
		}
		rs();
		return s;
	}
	void rn(){
		rec();
		c = nc = 0;
	}
};

Buc a[MX / B + 1];

int main(){
	scanf("%d%d%d", &n, &q, &K);
	for(int i = 0; i < n; i++){
		scanf("%d", a[i / B].a + (i % B));
		a[i / B].s += a[i / B].a[i % B];
	}
	for(int t, x, y; q--; ){
		scanf("%d%d%d", &t, &x, &y);
		if(t == 1){
			x--;
			a[x / B].rn();
			a[x / B].ch(x % B, y);
		}
		else if(t == 2){
			x--; y--;
			if(x % B) a[x / B].rn();
			for(; x <= y && x % B; x++) a[x / B].dv(x % B);
			for(; x + B <= y; x += B) a[x / B].nc++;
			if(x <= y) a[x / B].rn();
			for(; x <= y; x++) a[x / B].dv(x % B);
		}
		else{
			x--; y--;
			ll ans = 0;
			if(x % B) a[x / B].rec(); 
			for(; x <= y && x % B; x++) ans += a[x / B].a[x % B];
			for(; x + B <= y; x += B) ans += a[x / B].rec();
			if(x <= y) a[x / B].rec();
			for(; x <= y; x++) ans += a[x / B].a[x % B];
			printf("%lld\n", ans);
		}
		//for(int i = 0; i < n; i++) printf("%d ", a[i / B].a[i % B]);
		//puts("");
	}
	//puts("");
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:34:29: 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:36:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a[i / B].a + (i % B));
                                    ^
sterilizing.cpp:40:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &x, &y);
                              ^

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