oj.uz

Submission #25112

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

const int MX = 100000, B = 50;
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 2440 KB Output is correct
2 Correct 0 ms 2440 KB Output is correct
3 Correct 0 ms 2440 KB Output is correct
4 Correct 3 ms 2440 KB Output is correct
5 Correct 3 ms 2440 KB Output is correct
6 Correct 3 ms 2440 KB Output is correct
7 Correct 3 ms 2440 KB Output is correct
8 Correct 3 ms 2440 KB Output is correct
9 Correct 6 ms 2440 KB Output is correct
10 Correct 6 ms 2440 KB Output is correct
11 Correct 6 ms 2440 KB Output is correct
12 Correct 6 ms 2440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 913 ms 2440 KB Output is correct
2 Correct 716 ms 2440 KB Output is correct
3 Correct 759 ms 2440 KB Output is correct
4 Correct 1103 ms 2440 KB Output is correct
5 Correct 1426 ms 2440 KB Output is correct
6 Correct 1413 ms 2440 KB Output is correct
7 Correct 1363 ms 2440 KB Output is correct
8 Correct 1346 ms 2440 KB Output is correct
9 Correct 3289 ms 2440 KB Output is correct
10 Correct 3156 ms 2440 KB Output is correct
11 Correct 3363 ms 2440 KB Output is correct
12 Correct 3203 ms 2440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2440 KB Output is correct
2 Correct 143 ms 2440 KB Output is correct
3 Correct 233 ms 2440 KB Output is correct
4 Correct 669 ms 2440 KB Output is correct
5 Correct 1379 ms 2440 KB Output is correct
6 Correct 1349 ms 2440 KB Output is correct
7 Correct 1319 ms 2440 KB Output is correct
8 Correct 1336 ms 2440 KB Output is correct
9 Correct 3219 ms 2440 KB Output is correct
10 Correct 3213 ms 2440 KB Output is correct
11 Correct 3169 ms 2440 KB Output is correct
12 Correct 3156 ms 2440 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 2440 KB Output is correct
2 Correct 819 ms 2440 KB Output is correct
3 Correct 433 ms 2440 KB Output is correct
4 Correct 766 ms 2440 KB Output is correct
5 Correct 1383 ms 2440 KB Output is correct
6 Correct 1469 ms 2440 KB Output is correct
7 Correct 1483 ms 2440 KB Output is correct
8 Correct 1396 ms 2440 KB Output is correct
9 Correct 3213 ms 2440 KB Output is correct
10 Correct 3239 ms 2440 KB Output is correct
11 Correct 3246 ms 2440 KB Output is correct
12 Correct 3199 ms 2440 KB Output is correct