oj.uz

Submission #46436

# Submission time Handle Problem Language Result Execution time Memory
46436 2018-04-20T16:06:48 Z RezwanArefin01 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 6716 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) 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 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 7 ms 560 KB Output is correct
5 Correct 7 ms 772 KB Output is correct
6 Correct 5 ms 772 KB Output is correct
7 Correct 6 ms 772 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 7 ms 772 KB Output is correct
10 Correct 8 ms 772 KB Output is correct
11 Correct 6 ms 772 KB Output is correct
12 Correct 6 ms 772 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5082 ms 3288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3288 KB Output is correct
2 Correct 18 ms 3372 KB Output is correct
3 Correct 26 ms 3388 KB Output is correct
4 Correct 70 ms 3388 KB Output is correct
5 Correct 144 ms 6204 KB Output is correct
6 Correct 117 ms 6204 KB Output is correct
7 Execution timed out 5030 ms 6204 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6204 KB Output is correct
2 Correct 134 ms 6204 KB Output is correct
3 Correct 145 ms 6204 KB Output is correct
4 Correct 168 ms 6204 KB Output is correct
5 Correct 204 ms 6488 KB Output is correct
6 Correct 214 ms 6524 KB Output is correct
7 Correct 191 ms 6524 KB Output is correct
8 Correct 287 ms 6588 KB Output is correct
9 Correct 210 ms 6588 KB Output is correct
10 Correct 235 ms 6588 KB Output is correct
11 Correct 173 ms 6588 KB Output is correct
12 Correct 323 ms 6716 KB Output is correct