oj.uz

Submission #557011

# Submission time Handle Problem Language Result Execution time Memory
557011 2022-05-04T14:35:53 Z rainboy Sterilizing Spray (JOI15_sterilizing) C
10 / 100
 87 ms 5332 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 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 340 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 49 ms 3720 KB Output is correct
2 Correct 40 ms 3116 KB Output is correct
3 Correct 36 ms 4132 KB Output is correct
4 Correct 51 ms 4924 KB Output is correct
5 Correct 83 ms 5332 KB Output is correct
6 Correct 57 ms 5324 KB Output is correct
7 Correct 55 ms 5280 KB Output is correct
8 Correct 55 ms 5320 KB Output is correct
9 Correct 61 ms 5196 KB Output is correct
10 Correct 59 ms 5200 KB Output is correct
11 Correct 51 ms 5184 KB Output is correct
12 Correct 53 ms 5196 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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