oj.uz

Submission #469996

# Submission time Handle Problem Language Result Execution time Memory
469996 2021-09-02T13:55:18 Z rainboy Deda (COCI17_deda) C
140 / 140
 125 ms 6716 KB 
#include <stdio.h>
#include <string.h>

#define N	200000
#define N_	(1 << 18)

int min(int a, int b) { return a < b ? a : b; }

int st[N_ * 2], n_;

void build(int n) {
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	memset(st, 0x3f, n_ * 2 * sizeof *st);
}

void pul(int i) {
	st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
}

void update(int i, int x) {
	st[i += n_] = x;
	while (i > 1)
		pul(i >>= 1);
}

int query(int l, int x) {
	int r = n_ - 1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (st[l] <= x) {
				while (l < n_)
					l = st[l << 1 | 0] <= x ? l << 1 | 0 : l << 1 | 1;
				return l - n_ + 1;
			}
			l++;
		}
	return -1;
}

int main() {
	int n, q;

	scanf("%d%d", &n, &q);
	build(n);
	while (q--) {
		static char s[2];
		int i, x;

		scanf("%s", s);
		if (s[0] == 'M') {
			scanf("%d%d", &x, &i), i--;
			update(i, x);
		} else {
			scanf("%d%d", &x, &i), i--;
			printf("%d\n", query(i, x));
		}
	}
	return 0;
}

Compilation message

deda.c: In function 'main':
deda.c:46:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
deda.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
deda.c:54:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |    scanf("%d%d", &x, &i), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
deda.c:57:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |    scanf("%d%d", &x, &i), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 125 ms 6716 KB Output is correct
5 Correct 102 ms 5212 KB Output is correct
6 Correct 112 ms 6556 KB Output is correct
7 Correct 109 ms 6640 KB Output is correct