oj.uz

Submission #557019

# Submission time Handle Problem Language Result Execution time Memory
557019 2022-05-04T14:44:39 Z rainboy Sterilizing Spray (JOI15_sterilizing) C
10 / 100
 71 ms 2968 KB 
#include <stdio.h>

#define N	200000
#define N_	(1 << 18)	/* 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 upd(int i, int x) {
	i += n_;
	st[i] = x;
	while (i > 1)
		pul(i >>= 1);
}

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) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			update_(l++);
		if ((r & 1) == 0)
			update_(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:67:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d%d%d", &n, &q, &d);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.c:69:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
sterilizing.c:74:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
sterilizing.c:76:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |    scanf("%d%d", &i, &x), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
sterilizing.c:79:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1868 KB Output is correct
2 Correct 40 ms 1564 KB Output is correct
3 Correct 36 ms 2488 KB Output is correct
4 Correct 44 ms 2792 KB Output is correct
5 Correct 57 ms 2892 KB Output is correct
6 Correct 52 ms 2948 KB Output is correct
7 Correct 56 ms 2844 KB Output is correct
8 Correct 52 ms 2836 KB Output is correct
9 Correct 50 ms 2908 KB Output is correct
10 Correct 49 ms 2868 KB Output is correct
11 Correct 51 ms 2968 KB Output is correct
12 Correct 51 ms 2852 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 1568 KB Output isn't correct
2 Halted 0 ms 0 KB -