Submission #707734

#	Time	Username	Problem	Language	Result	Execution time	Memory
707734		rainboy	Fire (JOI20_ho_t5)	C11	100 / 100	446 ms	73672 KiB

ho_t5

#include <stdio.h>

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

typedef unsigned long long ull;

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

unsigned int X = 12345;

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

void ft_update(ull *ft, int n, int i, ull x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

ull ft_query(ull *ft, int i) {
	ull x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int st[N_ * 2], n_;

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

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		st[n_ + i] = i < n ? aa[i] : 0;
	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 = 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 type[M], tt[M], ll[M], rr[M], ii[M], m; ull xx[M], yy[M];

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) {
			int c = tt[hh[j]] != tt[h] ? tt[hh[j]] - tt[h] : type[hh[j]] - type[h];

			if (c == 0)
				j++;
			else if (c < 0) {
				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;
	}
}

void add_upd0(int t, int i, ull x) {
	type[m] = 0, tt[m] = t, ii[m] = i, xx[m] = x, m++;
}

void add_upd1(int t, int i, ull x, ull y) {
	type[m] = 1, tt[m] = t, ii[m] = i, xx[m] = x, yy[m] = y, m++;
}

void add_query(int t, int l, int r) {
	type[m] = 2, tt[m] = t, ll[m] = l, rr[m] = r, m++;
}

int main() {
	static int aa[N], qu[N], pp[N], qq[N], hh[M];
	static ull ft1[N], ft2[N], ft3[N], ans[Q];
	int n, q, cnt, h, h_, i, t, l, r;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	st_build(aa, n);
	cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt && aa[qu[cnt - 1]] <= aa[i])
			cnt--;
		pp[i] = cnt == 0 ? -1 : qu[cnt - 1];
		qu[cnt++] = i;
	}
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			cnt--;
		qq[i] = cnt == 0 ? n : qu[cnt - 1];
		qu[cnt++] = i;
	}
	for (h = 0; h < q; h++) {
		scanf("%d%d%d", &t, &l, &r), l--, r--;
		add_query(t, l, r);
	}
	for (i = 0; i < n; i++)
		if (pp[i] == -1) {
			add_upd0(0, i, (ull) -i * aa[i]);
			add_upd1(0, i + 1, (ull) (i + 1) * aa[i], aa[i]);
			add_upd1(qq[i] - i, i + 1, (ull) -(i + 1) * aa[i], -aa[i]);
			add_upd0(qq[i] - i, qq[i], (ull) qq[i] * aa[i]);
		} else {
			add_upd0(0, i, (ull) -i * aa[i]);
			add_upd0(i - pp[i], i, (ull) i * aa[i]);
			add_upd1(i - pp[i], pp[i] + 1, (ull) -(pp[i] + 1) * aa[i], -aa[i]);
			add_upd1(qq[i] - pp[i], pp[i] + 1, (ull) (pp[i] + 1) * aa[i], aa[i]);
			add_upd1(0, i + 1, (ull) (i + 1) * aa[i], aa[i]);
			add_upd1(qq[i] - i, i + 1, (ull) -(i + 1) * aa[i], -aa[i]);
			add_upd0(qq[i] - i, qq[i], (ull) qq[i] * aa[i]);
			add_upd0(qq[i] - pp[i], qq[i], (ull) -qq[i] * aa[i]);
		}
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (type[h_] == 0)
			ft_update(ft1, n, ii[h_], xx[h_]);
		else if (type[h_] == 1) {
			ft_update(ft2, n, ii[h_], xx[h_]);
			ft_update(ft3, n, ii[h_], yy[h_]);
		} else {
			ans[h_] += ft_query(ft1, rr[h_]) - ft_query(ft1, ll[h_]);
			ans[h_] += ft_query(ft2, rr[h_] - tt[h_]) - ft_query(ft2, ll[h_] - tt[h_]);
			ans[h_] += (ft_query(ft3, rr[h_] - tt[h_]) - ft_query(ft3, ll[h_] - tt[h_])) * tt[h_];
			ans[h_] += (ull) st_query(max(rr[h_] - tt[h_], 0), rr[h_]) * (rr[h_] + 1);
			ans[h_] -= (ull) st_query(max(ll[h_] - tt[h_], 0), ll[h_]) * ll[h_];
		}
	}
	for (h = 0; h < q; h++)
		printf("%llu\n", ans[h]);
	return 0;
}

Compilation message (stderr)

ho_t5.c: In function 'main':
ho_t5.c:102:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
ho_t5.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
ho_t5.c:121:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%d%d%d", &t, &l, &r), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80