oj.uz

Submission #557025

# Submission time Handle Problem Language Result Execution time Memory
557025 2022-05-04T15:05:27 Z rainboy Sterilizing Spray (JOI15_sterilizing) C
100 / 100
 209 ms 5104 KB 
#include <stdio.h>
 
#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N))) */
 
long long st[N_ * 2]; int n_, d;
 
void pul(int i) {
	st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}
 
void build(int *aa, int n) {
	int i;
 
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		st[n_ + i] = aa[i];
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}
 
void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void upd(int i, int x) {
	i += n_, st[i] = x, pull(i);
}
 
void update_(int i) {
	if (st[i] == 0)
		return;
	if (i >= n_) {
		st[i] /= d;
		return;
	}
	update_(i << 1 | 0), update_(i << 1 | 1);
	pul(i);
}
 
void update(int l, int r) {
	int l_ = l += n_, r_ = r += n_;

	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			update_(l++);
		if ((r & 1) == 0)
			update_(r--);
	}
	pull(l_), pull(r_);
}
 
long long query(int l, int r) {
	long long x = 0;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x += st[l++];
		if ((r & 1) == 0)
			x += st[r--];
	}
	return x;
}
 
int main() {
	static int aa[N];
	int n, q, i;
 
	scanf("%d%d%d", &n, &q, &d);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	build(aa, n);
	while (q--) {
		int t, x, l, r;
 
		scanf("%d", &t);
		if (t == 1) {
			scanf("%d%d", &i, &x), i--;
			upd(i, x);
		} else {
			scanf("%d%d", &l, &r), l--, r--;
			if (t == 2) {
				if (d > 1)
					update(l, r);
			} else
				printf("%lld\n", query(l, r));
		}
	}
	return 0;
}

Compilation message

sterilizing.c: In function 'main':
sterilizing.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d%d", &n, &q, &d);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.c:74:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
sterilizing.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
sterilizing.c:81:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |    scanf("%d%d", &i, &x), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
sterilizing.c:84:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1728 KB Output is correct
2 Correct 42 ms 1472 KB Output is correct
3 Correct 38 ms 2432 KB Output is correct
4 Correct 45 ms 2808 KB Output is correct
5 Correct 57 ms 2936 KB Output is correct
6 Correct 56 ms 2856 KB Output is correct
7 Correct 56 ms 2888 KB Output is correct
8 Correct 62 ms 2848 KB Output is correct
9 Correct 56 ms 2868 KB Output is correct
10 Correct 52 ms 2924 KB Output is correct
11 Correct 49 ms 2960 KB Output is correct
12 Correct 54 ms 2888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 448 KB Output is correct
2 Correct 13 ms 1308 KB Output is correct
3 Correct 18 ms 1236 KB Output is correct
4 Correct 49 ms 888 KB Output is correct
5 Correct 67 ms 2508 KB Output is correct
6 Correct 63 ms 2496 KB Output is correct
7 Correct 47 ms 2540 KB Output is correct
8 Correct 65 ms 2480 KB Output is correct
9 Correct 59 ms 3152 KB Output is correct
10 Correct 59 ms 3768 KB Output is correct
11 Correct 58 ms 3780 KB Output is correct
12 Correct 60 ms 3740 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1464 KB Output is correct
2 Correct 82 ms 1600 KB Output is correct
3 Correct 94 ms 1356 KB Output is correct
4 Correct 105 ms 1100 KB Output is correct
5 Correct 123 ms 2624 KB Output is correct
6 Correct 143 ms 2676 KB Output is correct
7 Correct 137 ms 2652 KB Output is correct
8 Correct 163 ms 2780 KB Output is correct
9 Correct 155 ms 3568 KB Output is correct
10 Correct 172 ms 5024 KB Output is correct
11 Correct 126 ms 5012 KB Output is correct
12 Correct 209 ms 5104 KB Output is correct