oj.uz

Submission #34587

# Submission time Handle Problem Language Result Execution time Memory
34587 2017-11-14T02:47:16 Z sinhriv Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 299 ms 12216 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, K, m;
long long pw[N];

struct SegmentTree{
	int mx[N << 3];
	long long sum[N << 3];

	#define mid ((l + r) >> 1)

	void modify(int x, int l, int r, int u, int val){
		if(l > u || r < u) return;
		if(l == r){
			sum[x] = mx[x] = val;
			return;
		}
		modify(x + x, l, mid, u, val);
		modify(x + x + 1, mid + 1, r, u, val);

		sum[x] = sum[x + x] + sum[x + x + 1];
		mx[x] = max(mx[x + x], mx[x + x + 1]);
	}

	void update(int x, int l, int r, int u, int v){
		if(l > v || r < u || mx[x] == 0) return;
		if(l == r){
			sum[x] /= K;
			mx[x] /= K;
			return;
		}
		update(x + x, l, mid, u, v);
		update(x + x + 1, mid + 1, r, u, v);
		sum[x] = sum[x + x] + sum[x + x + 1];
		mx[x] = max(mx[x + x], mx[x + x + 1]);
	}

	long long query(int x, int l, int r, int u, int v){
		if(l > v || r < u) return 0;
		if(l >= u && r <= v) return sum[x];	
		return query(x + x, l, mid, u, v) + query(x + x + 1, mid + 1, r, u, v);
	}
}Smt;

int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	scanf("%d%d%d", &n, &m, &K);


	pw[0] = 1;
	for(int i = 1; i <= m; ++i){
		if(1e18 / pw[i - 1] < K) pw[i] = 1e18;
		else pw[i] = pw[i - 1] * K;
	}


	for(int i = 1; i <= n; ++i){
		int x;
		scanf("%d", &x);
		Smt.modify(1, 1, n, i, x);
	}


	while(m--){
		int t, u, v;
		scanf("%d%d%d", &t, &u, &v);


		if(t == 1){
			Smt.modify(1, 1, n, u, v);
		}
		if(t == 2 && K > 1){
			Smt.update(1, 1, n, u, v);
		}


		if(t == 3){
			printf("%lld\n", Smt.query(1, 1, n, u, v));
		}
	}

	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:51:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
sterilizing.cpp:54:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &K);
                             ^
sterilizing.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
sterilizing.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &u, &v);
                              ^

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 12216 KB Output is correct
2 Correct 66 ms 12216 KB Output is correct
3 Correct 73 ms 12216 KB Output is correct
4 Correct 86 ms 12216 KB Output is correct
5 Correct 103 ms 12216 KB Output is correct
6 Correct 119 ms 12216 KB Output is correct
7 Correct 113 ms 12216 KB Output is correct
8 Correct 113 ms 12216 KB Output is correct
9 Correct 116 ms 12216 KB Output is correct
10 Correct 109 ms 12216 KB Output is correct
11 Correct 96 ms 12216 KB Output is correct
12 Correct 106 ms 12216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12216 KB Output is correct
2 Correct 26 ms 12216 KB Output is correct
3 Correct 29 ms 12216 KB Output is correct
4 Correct 79 ms 12216 KB Output is correct
5 Correct 99 ms 12216 KB Output is correct
6 Correct 113 ms 12216 KB Output is correct
7 Correct 103 ms 12216 KB Output is correct
8 Correct 99 ms 12216 KB Output is correct
9 Correct 109 ms 12216 KB Output is correct
10 Correct 96 ms 12216 KB Output is correct
11 Correct 103 ms 12216 KB Output is correct
12 Correct 109 ms 12216 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 12216 KB Output is correct
2 Correct 139 ms 12216 KB Output is correct
3 Correct 136 ms 12216 KB Output is correct
4 Correct 156 ms 12216 KB Output is correct
5 Correct 196 ms 12216 KB Output is correct
6 Correct 223 ms 12216 KB Output is correct
7 Correct 216 ms 12216 KB Output is correct
8 Correct 253 ms 12216 KB Output is correct
9 Correct 243 ms 12216 KB Output is correct
10 Correct 229 ms 12216 KB Output is correct
11 Correct 179 ms 12216 KB Output is correct
12 Correct 299 ms 12216 KB Output is correct