oj.uz

Submission #46438

# Submission time Handle Problem Language Result Execution time Memory
46438 2018-04-20T16:10:32 Z RezwanArefin01 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 405 ms 37740 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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 || mx[node] == 0) 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) {
			if(k == 1) continue;
			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:19: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:40: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:57: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:66: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:74: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:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:80: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 452 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 3 ms 452 KB Output is correct
4 Correct 7 ms 576 KB Output is correct
5 Correct 6 ms 644 KB Output is correct
6 Correct 7 ms 772 KB Output is correct
7 Correct 6 ms 772 KB Output is correct
8 Correct 7 ms 772 KB Output is correct
9 Correct 7 ms 772 KB Output is correct
10 Correct 6 ms 772 KB Output is correct
11 Correct 6 ms 864 KB Output is correct
12 Correct 6 ms 864 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3312 KB Output is correct
2 Correct 65 ms 4796 KB Output is correct
3 Correct 70 ms 8812 KB Output is correct
4 Correct 97 ms 11048 KB Output is correct
5 Correct 109 ms 13544 KB Output is correct
6 Correct 116 ms 15908 KB Output is correct
7 Correct 94 ms 18356 KB Output is correct
8 Correct 102 ms 20936 KB Output is correct
9 Correct 89 ms 23276 KB Output is correct
10 Correct 85 ms 25580 KB Output is correct
11 Correct 88 ms 27880 KB Output is correct
12 Correct 88 ms 30304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30304 KB Output is correct
2 Correct 19 ms 30304 KB Output is correct
3 Correct 26 ms 30304 KB Output is correct
4 Correct 70 ms 30304 KB Output is correct
5 Correct 98 ms 30848 KB Output is correct
6 Correct 112 ms 30848 KB Output is correct
7 Correct 81 ms 30848 KB Output is correct
8 Correct 96 ms 32192 KB Output is correct
9 Correct 82 ms 33564 KB Output is correct
10 Correct 86 ms 34724 KB Output is correct
11 Correct 95 ms 36020 KB Output is correct
12 Correct 79 ms 37428 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 37428 KB Output is correct
2 Correct 131 ms 37428 KB Output is correct
3 Correct 157 ms 37428 KB Output is correct
4 Correct 156 ms 37428 KB Output is correct
5 Correct 202 ms 37548 KB Output is correct
6 Correct 222 ms 37564 KB Output is correct
7 Correct 190 ms 37680 KB Output is correct
8 Correct 290 ms 37736 KB Output is correct
9 Correct 205 ms 37736 KB Output is correct
10 Correct 230 ms 37740 KB Output is correct
11 Correct 185 ms 37740 KB Output is correct
12 Correct 405 ms 37740 KB Output is correct