oj.uz

답안 #46434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46434 2018-04-20T16:00:47 Z RezwanArefin01 Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 322 ms 7684 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 && 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: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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 4312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 4312 KB Output is correct
2 Correct 18 ms 4312 KB Output is correct
3 Correct 26 ms 4312 KB Output is correct
4 Correct 74 ms 4312 KB Output is correct
5 Correct 106 ms 6764 KB Output is correct
6 Correct 109 ms 6772 KB Output is correct
7 Incorrect 110 ms 6772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 6772 KB Output is correct
2 Correct 134 ms 6772 KB Output is correct
3 Correct 151 ms 6772 KB Output is correct
4 Correct 167 ms 6772 KB Output is correct
5 Correct 197 ms 7540 KB Output is correct
6 Correct 231 ms 7632 KB Output is correct
7 Correct 188 ms 7632 KB Output is correct
8 Correct 322 ms 7684 KB Output is correct
9 Correct 208 ms 7684 KB Output is correct
10 Correct 238 ms 7684 KB Output is correct
11 Correct 181 ms 7684 KB Output is correct
12 Correct 314 ms 7684 KB Output is correct