oj.uz

Submission #46435

# Submission time Handle Problem Language Result Execution time Memory
46435 2018-04-20T16:05:16 Z RezwanArefin01 Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 378 ms 6512 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int maxn = 1e5 + 10; 
ll t[maxn << 2], mx[maxn << 2]; 
int a[maxn], lazy[maxn << 2], n, q, k; 

void build(int node, int l, int r) {
	if(l == r) {
		t[node] = a[l];
		mx[node] = a[l];
		return; 
	} int m = l + r >> 1;
	build(node << 1, l, m); 
	build(node << 1 | 1, m + 1, r); 
	t[node] = t[node << 1] + t[node << 1 | 1]; 
	mx[node] = max(mx[node << 1], mx[node << 1 | 1]); 
}

void shift(int node) {
	if(!lazy[node]) return; 
	t[node << 1] = mx[node << 1] = 0; 
	t[node << 1 | 1] = mx[node << 1 | 1] = 0; 
	lazy[node << 1] = lazy[node << 1 | 1] = 1;
	lazy[node] = 0;
}

void change(int node, int l, int r, int i, int x) {
	if(r < i || l > i) return;
	if(l == r) {
		t[node] = mx[node] = x; 
		return; 
	} shift(node); 
	int m = l + r >> 1;
	if(i <= m) change(node << 1, l, m, i, x);
	else change(node << 1 | 1, m + 1, r, i, x);
	t[node] = t[node << 1] + t[node << 1 | 1]; 
	mx[node] = max(mx[node << 1], mx[node << 1 | 1]); 
}

void update(int node, int l, int r, int i, int j) {
	if(r < i || l > j) return; 
	if(i <= l && r <= j && mx[node] < k) {
		t[node] = mx[node] = 0; 
		lazy[node] = 1; return; 
	}  
	if(l == r) {
		t[node] = mx[node] = t[node] / k;
		return; 
	} shift(node);
	int m = l + r >> 1;
	update(node << 1, l, m, i, j); 
	update(node << 1 | 1, m + 1, r, i, j); 
	t[node] = t[node << 1] + t[node << 1 | 1]; 
	mx[node] = max(mx[node << 1], mx[node << 1 | 1]); 
}
ll query(int node, int l, int r, int i, int j) {
	if(r < i || l > j) return 0; 
	if(i <= l && r <= j) return t[node]; 
	shift(node); int m = l + r >> 1;
	return query(node << 1, l, m, i, j) + 
		   query(node << 1 | 1, m + 1, r, i, j);
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	scanf("%d %d %d", &n, &q, &k); 
	for(int i = 1; i <= n; i++) 
		scanf("%d", &a[i]);
	build(1, 1, n);
	while(q--) {
		int t, l, r; 
		scanf("%d %d %d", &t, &l, &r); 
		if(t == 1) change(1, 1, n, l, r); 
		else if(t == 2 && k != 1) update(1, 1, n, l, r); 
		else printf("%lld\n", query(1, 1, n, l, r));
	}
}

Compilation message

sterilizing.cpp: In function 'void build(int, int, int)':
sterilizing.cpp:16:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  } int m = l + r >> 1;
            ~~^~~
sterilizing.cpp: In function 'void change(int, int, int, int, int)':
sterilizing.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
sterilizing.cpp: In function 'void update(int, int, int, int, int)':
sterilizing.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
sterilizing.cpp: In function 'll query(int, int, int, int, int)':
sterilizing.cpp:63:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  shift(node); int m = l + r >> 1;
                       ~~^~~
sterilizing.cpp: In function 'int main(int, const char**)':
sterilizing.cpp:71:7: 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:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t, &l, &r); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 3520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3520 KB Output is correct
2 Correct 22 ms 3520 KB Output is correct
3 Correct 33 ms 3520 KB Output is correct
4 Correct 90 ms 3520 KB Output is correct
5 Correct 137 ms 6164 KB Output is correct
6 Correct 131 ms 6180 KB Output is correct
7 Incorrect 104 ms 6180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 6180 KB Output is correct
2 Correct 162 ms 6180 KB Output is correct
3 Correct 182 ms 6180 KB Output is correct
4 Correct 183 ms 6180 KB Output is correct
5 Correct 240 ms 6348 KB Output is correct
6 Correct 263 ms 6484 KB Output is correct
7 Correct 233 ms 6484 KB Output is correct
8 Correct 327 ms 6512 KB Output is correct
9 Correct 259 ms 6512 KB Output is correct
10 Correct 287 ms 6512 KB Output is correct
11 Correct 217 ms 6512 KB Output is correct
12 Correct 378 ms 6512 KB Output is correct