oj.uz

Submission #25124

# Submission time Handle Problem Language Result Execution time Memory
25124 2017-06-20T07:16:26 Z 김동현(#1052) Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 2879 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]; }
	ll rec(){
		int fl;
		while(c <= 30 && c < nc){
			fl = 0;
			for(int i = 0; i < B; i++){
				if(a[i]){
					dv(i);
					fl = 1;
				}
			}
			if(!fl) break;
			c++;
		}
		if(!fl) c = nc = 0;
		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);
		}
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:38: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:40: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:44: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 6 ms 2440 KB Output is correct
9 Correct 3 ms 2440 KB Output is correct
10 Correct 3 ms 2440 KB Output is correct
11 Correct 3 ms 2440 KB Output is correct
12 Correct 3 ms 2440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 2440 KB Output is correct
2 Correct 646 ms 2440 KB Output is correct
3 Correct 566 ms 2440 KB Output is correct
4 Correct 773 ms 2440 KB Output is correct
5 Correct 956 ms 2440 KB Output is correct
6 Correct 976 ms 2440 KB Output is correct
7 Correct 986 ms 2440 KB Output is correct
8 Correct 946 ms 2440 KB Output is correct
9 Correct 1123 ms 2440 KB Output is correct
10 Correct 1106 ms 2440 KB Output is correct
11 Correct 1119 ms 2440 KB Output is correct
12 Correct 1093 ms 2440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2440 KB Output is correct
2 Correct 59 ms 2440 KB Output is correct
3 Correct 89 ms 2440 KB Output is correct
4 Correct 226 ms 2440 KB Output is correct
5 Correct 749 ms 2440 KB Output is correct
6 Correct 743 ms 2440 KB Output is correct
7 Correct 1143 ms 2440 KB Output is correct
8 Correct 703 ms 2440 KB Output is correct
9 Correct 2663 ms 2440 KB Output is correct
10 Correct 2599 ms 2440 KB Output is correct
11 Correct 2696 ms 2440 KB Output is correct
12 Correct 2853 ms 2440 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 2440 KB Output is correct
2 Correct 359 ms 2440 KB Output is correct
3 Correct 226 ms 2440 KB Output is correct
4 Correct 289 ms 2440 KB Output is correct
5 Correct 796 ms 2440 KB Output is correct
6 Correct 803 ms 2440 KB Output is correct
7 Correct 796 ms 2440 KB Output is correct
8 Correct 789 ms 2440 KB Output is correct
9 Correct 2773 ms 2440 KB Output is correct
10 Correct 2829 ms 2440 KB Output is correct
11 Correct 2879 ms 2440 KB Output is correct
12 Correct 2726 ms 2440 KB Output is correct