Submission #704748

#	Time	Username	Problem	Language	Result	Execution time	Memory
704748		rainboy	단층 (JOI16_ho_t5)	C11	100 / 100	877 ms	30464 KiB

2016_ho_t5

#include <stdio.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define Q	200000

long long uumn[N_ * 2], uumx[N_ * 2], vvmn[N_ * 2], vvmx[N_ * 2], ulz[N_], vlz[N_]; int h_, n_;

void put(int i, long long u, long long v) {
	uumn[i] += u, uumx[i] += u;
	vvmn[i] += v, vvmx[i] += v;
	if (i < n_)
		ulz[i] += u, vlz[i] += v;
}

void pus(int i) {
	if (ulz[i] || vlz[i])
		put(i << 1 | 0, ulz[i], vlz[i]), put(i << 1 | 1, ulz[i], vlz[i]), ulz[i] = vlz[i] = 0;
}

void pul(int i) {
	if (!ulz[i] && !vlz[i]) {
		int l = i << 1, r = l | 1;

		uumn[i] = uumn[l], uumx[i] = uumx[r];
		vvmn[i] = vvmn[l], vvmx[i] = vvmx[r];
	}
}

void build(int n) {
	int i;

	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++)
		uumn[n_ + i] = i, uumx[n_ + i] = i, vvmn[n_ + i] = i, vvmx[n_ + i] = i;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update(int l, int r, long long u, long long v) {
	int l_, r_;

	if (l > r)
		return;
	l_ = l += n_, r_ = r += n_;
	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, u, v);
		if ((r & 1) == 0)
			put(r--, u, v);
	}
	pull(l_), pull(r_);
}

int query_u(int u) {
	int i = 1;

	while (i < n_) {
		pus(i);
		if (uumx[i << 1 | 0] < u)
			i = i << 1 | 1;
		else
			i = i << 1 | 0;
	}
	return (uumx[i] < u ? i : i - 1) - n_;
}

int query_v(int v) {
	int i = 1;

	while (i < n_) {
		pus(i);
		if (vvmn[i << 1 | 1] >= v)
			i = i << 1 | 0;
		else
			i = i << 1 | 1;
	}
	return (vvmn[i] >= v ? i : i + 1) - n_;
}

int main() {
	static int tt[Q], xx[Q], vv[Q];
	int n, q, h, i;

	scanf("%d%d", &n, &q);
	for (h = 0; h < q; h++)
		scanf("%d%d%d", &xx[h], &tt[h], &vv[h]);
	build(n);
	for (h = q - 1; h >= 0; h--)
		if (tt[h] == 1)
			update(0, query_u(xx[h]), 0, -vv[h] * 2);
		else
			update(query_v(xx[h]), n_ - 1, vv[h] * 2, 0);
	for (i = 0; i < n_; i++)
		pus(i);
	for (i = 0; i < n; i++)
		printf("%lld\n", (uumn[n_ + i] - vvmn[n_ + i]) / 2);
	return 0;
}

Compilation message (stderr)

2016_ho_t5.c: In function 'main':
2016_ho_t5.c:101:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
2016_ho_t5.c:103:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d%d%d", &xx[h], &tt[h], &vv[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66