Submission #673689

#	Time	Username	Problem	Language	Result	Execution time	Memory
673689		rainboy	Two Dishes (JOI19_dishes)	C11	100 / 100	6075 ms	226264 KiB

dishes

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

#define N	1000000
#define M	1000000
#define N_	(1 << 20)	/* N_ = pow2(ceil(log2(M + 1))) */
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int *ej[N], *ev[N], eo[N];

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

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

long long st[N_ * 2], lz1[N_], lz2[N_]; int h_, n_;

void build(int n) {
	int i;

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

void put(int i, long long x, long long y) {
	st[i] = max(st[i], x);
	if (st[i] != -INF)
		st[i] += y;
	if (i < n_)
		lz1[i] = max(lz1[i], x - lz2[i]), lz2[i] += y;
}

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

void pul(int i) {
	if (lz1[i] == -INF && lz2[i] == 0)
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

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 x, long long y) {
	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, y);
		if ((r & 1) == 0)
			put(r--, x, y);
	}
	pull(l_), pull(r_);
}

long long query(int i) {
	push(i += n_);
	return st[i];
}

int main() {
	static long long aa[N], ss[N], bb[M], tt[M];
	static int pp[N], qq[M];
	int n, m, i, j, v, o, lower, upper;
	long long x;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%lld%lld%d", &aa[i], &ss[i], &pp[i]);
	for (i = 1; i < n; i++)
		aa[i] += aa[i - 1];
	for (j = 0; j < m; j++)
		scanf("%lld%lld%d", &bb[j], &tt[j], &qq[j]);
	for (j = 1; j < m; j++)
		bb[j] += bb[j - 1];
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ev[i] = (int *) malloc(2 * sizeof *ev[i]);
	}
	x = 0;
	for (i = 0; i < n; i++) {
		if (aa[i] > ss[i])
			continue;
		if (aa[i] + bb[m - 1] <= ss[i]) {
			x += pp[i];
			continue;
		}
		lower = -1, upper = m - 1;
		while (upper - lower > 1) {
			j = (lower + upper) / 2;
			if (aa[i] + bb[j] <= ss[i])
				lower = j;
			else
				upper = j;
		}
		j = upper;
		append(i, j, pp[i]);
	}
	for (j = 0; j < m; j++) {
		if (bb[j] > tt[j])
			continue;
		x += qq[j];
		if (aa[n - 1] + bb[j] <= tt[j])
			continue;
		lower = -1, upper = n - 1;
		while (upper - lower > 1) {
			i = (lower + upper) / 2;
			if (aa[i] + bb[j] <= tt[j])
				lower = i;
			else
				upper = i;
		}
		i = upper;
		append(i, j, -qq[j]);
	}
	build(m + 1);
	update(0, m, x, 0);
	for (i = 0; i < n; i++) {
		for (o = eo[i]; o--; ) {
			j = ej[i][o], v = ev[i][o];
			update(0, j, -INF, v);
		}
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			update(j + 1, m, query(j), 0);
		}
	}
	printf("%lld\n", query(m));
	return 0;
}

Compilation message (stderr)

dishes.c: In function 'append':
dishes.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
dishes.c: In function 'main':
dishes.c:92:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
dishes.c:94:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%lld%lld%d", &aa[i], &ss[i], &pp[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.c:98:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf("%lld%lld%d", &bb[j], &tt[j], &qq[j]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9