oj.uz

Submission #25106

# Submission time Handle Problem Language Result Execution time Memory
25106 2017-06-20T06:59:39 Z 김동현(#1052) Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 4649 ms 2800 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 2800 KB Output is correct
2 Correct 423 ms 2800 KB Output is correct
3 Correct 643 ms 2800 KB Output is correct
4 Correct 996 ms 2800 KB Output is correct
5 Correct 1269 ms 2800 KB Output is correct
6 Correct 1223 ms 2800 KB Output is correct
7 Correct 1269 ms 2800 KB Output is correct
8 Correct 1256 ms 2800 KB Output is correct
9 Correct 4479 ms 2800 KB Output is correct
10 Correct 4496 ms 2800 KB Output is correct
11 Correct 4566 ms 2800 KB Output is correct
12 Correct 4483 ms 2800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2800 KB Output is correct
2 Correct 99 ms 2800 KB Output is correct
3 Correct 179 ms 2800 KB Output is correct
4 Correct 389 ms 2800 KB Output is correct
5 Correct 1189 ms 2800 KB Output is correct
6 Correct 1343 ms 2800 KB Output is correct
7 Correct 1229 ms 2800 KB Output is correct
8 Correct 1193 ms 2800 KB Output is correct
9 Correct 4573 ms 2800 KB Output is correct
10 Correct 4536 ms 2800 KB Output is correct
11 Correct 4649 ms 2800 KB Output is correct
12 Correct 4529 ms 2800 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 2800 KB Output is correct
2 Correct 509 ms 2800 KB Output is correct
3 Correct 286 ms 2800 KB Output is correct
4 Correct 409 ms 2800 KB Output is correct
5 Correct 1293 ms 2800 KB Output is correct
6 Correct 1233 ms 2800 KB Output is correct
7 Correct 1269 ms 2800 KB Output is correct
8 Correct 1256 ms 2800 KB Output is correct
9 Correct 4466 ms 2800 KB Output is correct
10 Correct 4429 ms 2800 KB Output is correct
11 Correct 4543 ms 2800 KB Output is correct
12 Correct 4583 ms 2800 KB Output is correct