Submission #46436

#	Time	Username	Problem	Language	Result	Execution time	Memory
46436		RezwanArefin01	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5082 ms	6716 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75