oj.uz

Submission #25111

# Submission time Handle Problem Language Result Execution time Memory
25111 2017-06-20T07:05:44 Z kdh9949 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 3586 ms 2436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 100000, B = 60;
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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2436 KB Output is correct
2 Correct 0 ms 2436 KB Output is correct
3 Correct 0 ms 2436 KB Output is correct
4 Correct 3 ms 2436 KB Output is correct
5 Correct 9 ms 2436 KB Output is correct
6 Correct 3 ms 2436 KB Output is correct
7 Correct 6 ms 2436 KB Output is correct
8 Correct 3 ms 2436 KB Output is correct
9 Correct 3 ms 2436 KB Output is correct
10 Correct 6 ms 2436 KB Output is correct
11 Correct 3 ms 2436 KB Output is correct
12 Correct 6 ms 2436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 2436 KB Output is correct
2 Correct 766 ms 2436 KB Output is correct
3 Correct 849 ms 2436 KB Output is correct
4 Correct 1359 ms 2436 KB Output is correct
5 Correct 1576 ms 2436 KB Output is correct
6 Correct 1493 ms 2436 KB Output is correct
7 Correct 1516 ms 2436 KB Output is correct
8 Correct 1509 ms 2436 KB Output is correct
9 Correct 3586 ms 2436 KB Output is correct
10 Correct 3483 ms 2436 KB Output is correct
11 Correct 3353 ms 2436 KB Output is correct
12 Correct 3333 ms 2436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2436 KB Output is correct
2 Correct 166 ms 2436 KB Output is correct
3 Correct 273 ms 2436 KB Output is correct
4 Correct 706 ms 2436 KB Output is correct
5 Correct 1543 ms 2436 KB Output is correct
6 Correct 1539 ms 2436 KB Output is correct
7 Correct 1456 ms 2436 KB Output is correct
8 Correct 1509 ms 2436 KB Output is correct
9 Correct 3483 ms 2436 KB Output is correct
10 Correct 3439 ms 2436 KB Output is correct
11 Correct 3409 ms 2436 KB Output is correct
12 Correct 3393 ms 2436 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 2436 KB Output is correct
2 Correct 856 ms 2436 KB Output is correct
3 Correct 483 ms 2436 KB Output is correct
4 Correct 756 ms 2436 KB Output is correct
5 Correct 1583 ms 2436 KB Output is correct
6 Correct 1509 ms 2436 KB Output is correct
7 Correct 1409 ms 2436 KB Output is correct
8 Correct 1536 ms 2436 KB Output is correct
9 Correct 3416 ms 2436 KB Output is correct
10 Correct 3273 ms 2436 KB Output is correct
11 Correct 3349 ms 2436 KB Output is correct
12 Correct 3336 ms 2436 KB Output is correct