Submission #1276985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276985		kaiboy	Fire (JOI20_ho_t5)	C++20	100 / 100	682 ms	45292 KiB

ho_t5

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const int  N = 200000;
const int  Q = 200000;
const int N_ = 1 << 18;

int aa[N], qu[N], pp[N], qq[N];
int tt_[Q], ll_[Q], rr_[Q], zz[Q]; long long xx[Q];
int tt[N * 7], ll[N * 7], rr[N * 7], bb[N * 7], hh[N * 7];
long long st[2][N_ << 1], lz[2][N_]; int sz[N_ << 1], h_, n_;

void put(int z, int i, long long a) {
	st[z][i] += a * sz[i];
	if (i < n_)
		lz[z][i] += a;
}

void pus(int z, int i) {
	if (lz[z][i]) {
		int l = i << 1, r = l ^ 1;
		put(z, l, lz[z][i]);
		put(z, r, lz[z][i]);
		lz[z][i] = 0;
	}
}

void pul(int z, int i) {
	if (!lz[z][i]) {
		int l = i << 1, r = l ^ 1;
		st[z][i] = st[z][l] + st[z][r];
	}
}

void push(int z, int i) {
	for (int h = h_; h; h--)
		pus(z, i >> h);
}

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

void build(int n) {
	for (h_ = 0, n_ = 1; n_ < n; h_++, n_ <<= 1)
		;
	for (int i = 0; i < n_; i++)
		sz[i + n_] = 1;
	for (int i = n_ - 1; i; i--)
		sz[i] = sz[i << 1] << 1;
}

void update(int z, int l, int r, int a) {
	int l_ = l += n_, r_ = r += n_;
	push(z, l_), push(z, r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put(z, l++, a);
		if (!(r & 1))
			put(z, r--, a);
	}
	pull(z, l_), pull(z, r_);
}

long long query(int z, int l, int r) {
	long long a = 0;
	push(z, l += n_), push(z, r += n_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			a += st[z][l++];
		if (!(r & 1))
			a += st[z][r--];
	}
	return a;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int z = 0; z < q; z++)
		cin >> tt_[z] >> ll_[z] >> rr_[z], ll_[z]--, rr_[z]--, zz[z] = z;
	sort(zz, zz + q, [] (int z0, int z1) { return tt_[z0] < tt_[z1]; });
	for (int cnt = 0, i = 0; i < n; i++) {
		while (cnt && aa[qu[cnt - 1]] <= aa[i])
			cnt--;
		pp[i] = cnt ? qu[cnt - 1] : -1, qu[cnt++] = i;
	}
	for (int cnt = 0, i = n - 1; i >= 0; i--) {
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			cnt--;
		qq[i] = cnt ? qu[cnt - 1] : n, qu[cnt++] = i;
	}
	int m = 0; build(n);
	for (int i = 0; i < n; i++) {
		int a = aa[i], p = pp[i], q = qq[i];
		update(0, i, q - 1, a);
		if (p != -1) {
			tt[m] = q - p - 1, ll[m] = i, rr[m] = q - 1, bb[m] = -a, hh[m] = m, m++;
			tt[m] = i - p, ll[m] = -1, rr[m] = p, bb[m] = -a, hh[m] = m, m++;
			tt[m] = q - p - 1, ll[m] = -1, rr[m] = p, bb[m] = a, hh[m] = m, m++;
			tt[m] = i - p, ll[m] = 0, rr[m] = i - 1, bb[m] = a, hh[m] = m, m++;
			tt[m] = q - p - 1, ll[m] = 0, rr[m] = i - 1, bb[m] = -a, hh[m] = m, m++;
		}
		if (i + 1 < q) {
			update(1, i + 1, n - 1, -a);
			tt[m] = q - i - 1, ll[m] = i + 1, rr[m] = -1, bb[m] = a, hh[m] = m, m++;
			if (q < n) {
				update(0, q, n - 1, a);
				tt[m] = q - i - 1, ll[m] = q, rr[m] = n - 1, bb[m] = -a, hh[m] = m, m++;
			}
		}
	}
	sort(hh, hh + m, [] (int h0, int h1) { return tt[h0] < tt[h1]; });
	long long s = 0;
	for (int g = 0, y = 0; y < q; y++) {
		int z = zz[y], t_ = tt_[z], l_ = ll_[z], r_ = rr_[z];
		for (int h; g < m && tt[h = hh[g]] <= t_; g++) {
			int l = ll[h], r = rr[h], a = bb[h];
			if (l == -1)
				update(1, 0, r, a), s += a;
			else if (r == -1)
				update(1, l, n - 1, a);
			else
				update(0, l, r, a);
		}
		xx[z] = query(0, l_, r_);
		if (r_ < t_)
			xx[z] += s * (r_ - l_ + 1);
		else if (l_ < t_)
			xx[z] += s * (t_ - l_) + query(1, 0, r_ - t_);
		else
			xx[z] += query(1, l_ - t_, r_ - t_);
	}
	for (int z = 0; z < q; z++)
		cout << xx[z] << '\n';
	return 0;
}

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