Submission #744512

#	Time	Username	Problem	Language	Result	Execution time	Memory
744512		rainboy	Trading (IZhO13_trading)	C11	100 / 100	166 ms	12044 KiB

trading

#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 (stderr)

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 / 100