oj.uz

Submission #25107

# Submission time Handle Problem Language Result Execution time Memory
25107 2017-06-20T07:01:28 Z 김동현(#1052) Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 3323 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 6 ms 2440 KB Output is correct
7 Correct 6 ms 2440 KB Output is correct
8 Correct 6 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 9 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 893 ms 2440 KB Output is correct
2 Correct 736 ms 2440 KB Output is correct
3 Correct 719 ms 2440 KB Output is correct
4 Correct 1133 ms 2440 KB Output is correct
5 Correct 1426 ms 2440 KB Output is correct
6 Correct 1366 ms 2440 KB Output is correct
7 Correct 1416 ms 2440 KB Output is correct
8 Correct 1373 ms 2440 KB Output is correct
9 Correct 3103 ms 2440 KB Output is correct
10 Correct 3129 ms 2440 KB Output is correct
11 Correct 3223 ms 2440 KB Output is correct
12 Correct 3323 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 153 ms 2440 KB Output is correct
3 Correct 226 ms 2440 KB Output is correct
4 Correct 683 ms 2440 KB Output is correct
5 Correct 1446 ms 2440 KB Output is correct
6 Correct 1373 ms 2440 KB Output is correct
7 Correct 1423 ms 2440 KB Output is correct
8 Correct 1466 ms 2440 KB Output is correct
9 Correct 3253 ms 2440 KB Output is correct
10 Correct 3119 ms 2440 KB Output is correct
11 Correct 3219 ms 2440 KB Output is correct
12 Correct 3199 ms 2440 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 2440 KB Output is correct
2 Correct 803 ms 2440 KB Output is correct
3 Correct 466 ms 2440 KB Output is correct
4 Correct 756 ms 2440 KB Output is correct
5 Correct 1449 ms 2440 KB Output is correct
6 Correct 1359 ms 2440 KB Output is correct
7 Correct 1429 ms 2440 KB Output is correct
8 Correct 1403 ms 2440 KB Output is correct
9 Correct 3263 ms 2440 KB Output is correct
10 Correct 3249 ms 2440 KB Output is correct
11 Correct 3183 ms 2440 KB Output is correct
12 Correct 3146 ms 2440 KB Output is correct