oj.uz

Submission #744512

# Submission time Handle Problem Language Result Execution time Memory
744512 2023-05-18T16:05:38 Z rainboy Trading (IZhO13_trading) C
100 / 100
 166 ms 12044 KB 
#include <stdio.h>

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define INF	0x3f3f3f3f

int max(int a, int b) { return a > b ? a : b; }

int st[N_ * 2], n_;

void build(int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 1; i < n_ * 2; i++)
		st[i] = -INF;
	for (i = 0; i < n; i++)
		st[n_ + i] = -i;
}

void update(int l, int r, int x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l] = max(st[l], x), l++;
		if ((r & 1) == 0)
			st[r] = max(st[r], x), r--;
	}
}

int main() {
	int n, m, i, l, r, x;

	scanf("%d%d", &n, &m);
	build(n);
	while (m--) {
		scanf("%d%d%d", &l, &r, &x), l--, r--;
		update(l, r, x - l);
	}
	for (i = 1; i < n_; i++) {
		l = i << 1, r = l | 1;
		st[l] = max(st[l], st[i]), st[r] = max(st[r], st[i]);
	}
	for (i = 0; i < n; i++)
		printf("%d ", st[n_ + i] + i);
	printf("\n");
	return 0;
}

Compilation message

trading.c: In function 'main':
trading.c:35:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
trading.c:38:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d%d%d", &l, &r, &x), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 80 ms 5960 KB Output is correct
8 Correct 91 ms 6656 KB Output is correct
9 Correct 86 ms 6660 KB Output is correct
10 Correct 98 ms 6680 KB Output is correct
11 Correct 102 ms 7432 KB Output is correct
12 Correct 110 ms 7500 KB Output is correct
13 Correct 110 ms 7824 KB Output is correct
14 Correct 116 ms 7688 KB Output is correct
15 Correct 123 ms 8456 KB Output is correct
16 Correct 131 ms 8536 KB Output is correct
17 Correct 166 ms 10628 KB Output is correct
18 Correct 136 ms 11084 KB Output is correct
19 Correct 135 ms 10792 KB Output is correct
20 Correct 156 ms 12044 KB Output is correct