Submission #673673

#	Time	Username	Problem	Language	Result	Execution time	Memory
673673		rainboy	Two Antennas (JOI19_antennas)	C11	100 / 100	653 ms	37568 KiB

antennas

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

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

int *eh[N], eo[N], *ei[N], eo_[N];

void append(int **ej, int *eo, int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int st[N_ * 2], mn[N_ * 2], lz[N_ * 2], h_, n_;

void init() {
	int i;

	for (i = 1; i < n_ * 2; i++)
		st[i] = -INF, mn[i] = INF, lz[i] = -INF;
}

void put(int i, int x) {
	lz[i] = max(lz[i], x);
	st[i] = max(st[i], lz[i] == -INF || mn[i] == INF ? -INF : lz[i] - mn[i]);
}

void pus(int i) {
	if (lz[i] != -INF)
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = -INF;
}

void pul(int i) {
	if (lz[i] == -INF) {
		int l = i << 1, r = l | 1;

		st[i] = max(st[l], st[r]);
		mn[i] = min(mn[l], mn[r]);
	}
}

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 update1(int i, int x) {
	i += n_;
	push(i);
	st[i] = -INF, mn[i] = x, lz[i] = -INF;
	pull(i);
}

void update2(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

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

void update3(int i) {
	i += n_;
	push(i);
	st[i] = lz[i] == -INF || mn[i] == INF ? -INF : lz[i] - mn[i], mn[i] = INF;
	pull(i);
}

int query(int l, int r) {
	int x;

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

int main() {
	static int yy[N], aa[N], bb[N], ll[Q], rr[Q], ans[Q];
	int n, q, h, i, r, t, o, o_;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (i = 0; i < n; i++)
		scanf("%d%d%d", &yy[i], &aa[i], &bb[i]);
	scanf("%d", &q);
	for (h = 0; h < q; h++) {
		scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
		append(eh, eo, rr[h], h);
	}
	for (i = 0; i < n; i++)
		ei[i] = (int *) malloc(2 * sizeof *ei[i]);
	for (i = 0; i < n; i++) {
		if (i + aa[i] < n)
			append(ei, eo_, i + aa[i], i << 1 | 0);
		if (i + bb[i] + 1 < n)
			append(ei, eo_, i + bb[i] + 1, i << 1 | 1);
	}
	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	memset(ans, -1, q * sizeof *ans);
	for (t = 0; t < 2; t++) {
		init();
		for (r = 0; r < n; r++) {
			for (o_ = eo_[r]; o_--; ) {
				i = ei[r][o_];
				if ((i & 1) == 0)
					update1(i >> 1, yy[i >> 1]);
				else
					update3(i >> 1);
			}
			for (o = eo[r]; o--; ) {
				h = eh[r][o];
				ans[h] = max(ans[h], query(ll[h], r));
			}
			if (r - aa[r] >= 0)
				update2(max(r - bb[r], 0), r - aa[r], yy[r]);
			for (o = eo[r]; o--; ) {
				h = eh[r][o];
				ans[h] = max(ans[h], query(ll[h], r));
			}
		}
		for (i = 0; i < n; i++)
			yy[i] = -yy[i];
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

antennas.c: In function 'append':
antennas.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
antennas.c: In function 'main':
antennas.c:108:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
antennas.c:112:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d%d%d", &yy[i], &aa[i], &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.c:113:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
antennas.c:115:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65