Submission #708515

#	Time	Username	Problem	Language	Result	Execution time	Memory
708515		rainboy	Dungeon 3 (JOI21_ho_t5)	C11	100 / 100	948 ms	40928 KiB

Main

/* https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t5-review.pdf */
#include <stdio.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define N4	(N * 4 + 1)
#define M	200000

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

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int dd[N], cc[N], kk[N], n; long long xx[N + 1];
int ll[M], ll1[M * 2], rr[M], tt[M], m; long long ans[M];

int st[N_ * 2], n_;

void build(int *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		st[n_ + i] = aa[i];
	for (i = n_ - 1; i > 0; i--)
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

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

	x = 0;
	for (l += n_, r += n_; 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 *vv;

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (vv[hh[j]] == vv[h])
				j++;
			else if (vv[hh[j]] < vv[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int zz[N4], ll_[N4], rr_[N4], u_, l_, r_; long long xx_[N4], aa[N4], aa_[N4], bb[N4], bb_[N4];

int node(long long x, long long a, long long b) {
	static int _ = 1;

	zz[_] = rand_();
	xx_[_] = x, aa_[_] = aa[_] = a, bb_[_] = bb[_] = b;
	return _++;
}

void pul(int u) {
	int l = ll_[u], r = rr_[u];

	aa_[u] = aa_[l] + aa[u] + aa_[r], bb_[u] = bb_[l] + bb[u] + bb_[r];
}

void split(int u, long long x) {
	if (u == 0) {
		u_ = u, l_ = r_ = 0;
		return;
	}
	if (xx_[u] < x) {
		split(rr_[u], x);
		rr_[u] = l_, l_ = u;
	} else if (xx_[u] > x) {
		split(ll_[u], x);
		ll_[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll_[u], r_ = rr_[u];
		ll_[u] = rr_[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr_[u] = merge(rr_[u], v), pul(u);
		return u;
	} else {
		ll_[v] = merge(u, ll_[v]), pul(v);
		return v;
	}
}

void tr_update(long long x, long long a, long long b) {
	split(u_, x);
	if (u_ == 0)
		u_ = node(x, a, b);
	else
		aa_[u_] = aa[u_] += a, bb_[u_] = bb[u_] += b;
	u_ = merge(merge(l_, u_), r_);
}

long long tr_query(long long x) {
	int u;
	long long a, b;

	u = u_, a = 0, b = 0;
	while (u)
		if (xx_[u] <= x)
			a += aa_[u] - aa_[rr_[u]], b += bb_[u] - bb_[rr_[u]], u = rr_[u];
		else
			u = ll_[u];
	return a * x + b;
}

int main() {
	static int qu[N], hh[M], hh_[M * 2];
	int m_, cnt, g, h, h_, i, j, lower, upper;

	scanf("%d%d", &n, &m);
	xx[0] = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &dd[i]);
		xx[i + 1] = xx[i] + dd[i];
	}
	build(dd, n);
	for (i = 0; i < n; i++)
		scanf("%d", &cc[i]);
	for (h = 0; h < m; h++)
		scanf("%d%d%d", &ll[h], &rr[h], &tt[h]), ll[h]--, rr[h]--;
	for (h = 0; h < m; h++)
		hh[h] = h;
	vv = rr, sort(hh, 0, m);
	cnt = 0, m_ = 0;
	for (h = 0, i = 0; i <= n; i++) {
		while (h < m && rr[h_ = hh[h]] == i) {
			if (tt[h_] < st_query(ll[h_], rr[h_] - 1))
				ans[h_] = -1;
			else {
				lower = -1, upper = cnt - 1;
				while (upper - lower > 1) {
					g = (lower + upper) / 2;
					if (qu[g] >= ll[h_] && xx[i] - xx[qu[g]] <= tt[h_])
						upper = g;
					else
						lower = g;
				}
				g = upper;
				ans[h_] += (xx[i] - xx[qu[g]]) * cc[qu[g]];
				ll1[h_ << 1 | 0] = ll[h_], hh_[m_++] = h_ << 1 | 0;
				ll1[h_ << 1 | 1] = qu[g], hh_[m_++] = h_ << 1 | 1;
			}
			h++;
		}
		if (i < n) {
			while (cnt && cc[qu[cnt - 1]] > cc[i])
				cnt--;
			qu[cnt++] = i;
		}
	}
	vv = ll1, sort(hh_, 0, m_);
	cnt = 0;
	for (i = n, h = m_ - 1; i >= 0; i--) {
		if (i < n) {
			while (cnt && cc[j = qu[cnt - 1]] >= cc[i]) {
				tr_update(xx[j] - xx[i], -cc[j], (xx[j] - xx[i]) * cc[j]);
				tr_update(xx[kk[j]] - xx[i], cc[j], -(xx[kk[j]] - xx[i]) * cc[j]);
				cnt--;
			}
			kk[i] = cnt == 0 ? n : qu[cnt - 1];
			tr_update(0, cc[i], 0);
			tr_update(xx[kk[i]] - xx[i], -cc[i], (xx[kk[i]] - xx[i]) * cc[i]);
			qu[cnt++] = i;
		}
		while (h >= 0 && ll1[h_ = hh_[h]] == i) {
			ans[h_ >> 1] += tr_query(tt[h_ >> 1]) * ((h_ & 1) == 0 ? 1 : -1);
			h--;
		}
	}
	for (h = 0; h < m; h++)
		printf("%lld\n", ans[h]);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:142:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:145:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |   scanf("%d", &dd[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:150:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%d", &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:152:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d%d%d", &ll[h], &rr[h], &tt[h]), ll[h]--, rr[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44