Submission #1286272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286272		kaiboy	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	3021 ms	120356 KiB

Main

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

using namespace std;

const int  N = 200000;
const int  Q = 200000;
const int  M = N * 10;
const int M_ = 1 << 21;
const int N_ = 1 << 18;

long long aa[N + 1]; int cc[N + 1];
int ll[Q], rr[Q], dd[Q], zz[Q]; long long xx[Q];
int qu[N], pp[N], qq[N];
long long dd_[2][M], aa_[2][M], bb_[2][M]; int cc_[2][M], hh[2][M], mm[2], aa__[2];
long long st[2][M_ << 1], lz[2][M_], sz[2][M_ << 1]; int hh_[2], nn_[2];
long long ss[N];
int st_[N_ << 1], n__;

void append(int z, long long d, long long a, int c) {
	dd_[z][mm[z]] = d;
	aa_[z][mm[z]] = a;
	cc_[z][mm[z]] = c;
	hh[z][mm[z]] = mm[z];
	mm[z]++;
}

int compress(long long *aa, long long *bb, int n) {
	static int ii[M];
	for (int h = 0; h < n; h++)
		ii[h] = h;
	sort(ii, ii + n, [aa] (int i, int j) { return aa[i] < aa[j]; });
	int a_ = 0;
	for (int h = 0; h < n; h++) {
		int i = ii[h]; long long a = aa[i];
		bb[aa[i] = h + 1 == n || a < aa[ii[h + 1]] ? a_++ : a_] = a;
	}
	return a_;
}

void put(int z, int i, long long a) {
	st[z][i] += a * sz[z][i];
	if (i < nn_[z])
		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 = hh_[z]; h; h--)
		pus(z, i >> h);
}

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

void build(int z, int n) {
	int h_ = 0, n_ = 1;
	while (n_ < n)
		h_++, n_ <<= 1;
	hh_[z] = h_, nn_[z] = n_;
	for (int i = 0; i + 1 < n_; i++)
		sz[z][i + n_] = bb_[z][i + 1] - bb_[z][i];
	for (int i = n_ - 1; i; i--) {
		int l = i << 1, r = l ^ 1;
		sz[z][i] = sz[z][l] + sz[z][r];
	}
}

void update(int z, int l, int r, int a) {
	int l_ = l += nn_[z], r_ = r += nn_[z];
	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 += nn_[z]), push(z, r += nn_[z]);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			a += st[z][l++];
		if (!(r & 1))
			a += st[z][r--];
	}
	return a;
}

long long calc(int z, long long b) {
	int lower = -1, upper = aa__[z];
	while (upper - lower > 1) {
		int a = lower + upper >> 1;
		if (bb_[z][a] >= b)
			upper = a;
		else
			lower = a;
	}
	int a = upper;
	long long x = 0;
	if (a < aa__[z]) {
		x += query(z, a, aa__[z] - 1);
		if (a)
			x += query(z, a - 1, a - 1) / (bb_[z][a] - bb_[z][a - 1]) * (bb_[z][a] - b);
	}
	return x;
}

void pul(int i) {
	int l = i << 1, r = l ^ 1;
	st_[i] = max(st_[l], st_[r]);
}

void build(int n) {
	for (n__ = 1; n__ < n; n__ <<= 1)
		;
	for (int i = 0; i < n; i++)
		st_[i + n__] = aa[i + 1] - aa[i];
	for (int i = n__ - 1; i; i--)
		pul(i);
}

int query(int l, int r) {
	int a = 0;
	for (l += n__, r += n__; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			a = max(a, st_[l++]);
		if (!(r & 1))
			a = max(a, st_[r--]);
	}
	return a;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> aa[i], aa[i] += aa[i - 1];
	for (int i = 0; i < n; i++)
		cin >> cc[i];
	for (int z = 0; z < q; z++)
		cin >> ll[z] >> rr[z] >> dd[z], ll[z]--, rr[z]--, zz[z] = z;
	for (int cnt = 0, i = 0; i < n; i++) {
		while (cnt && cc[qu[cnt - 1]] >= cc[i])
			cnt--;
		pp[i] = cnt ? qu[cnt - 1] : -1, qu[cnt++] = i;
	}
	for (int cnt = 0, i = n - 1; i >= 0; i--) {
		while (cnt && cc[qu[cnt - 1]] > cc[i])
			cnt--;
		qq[i] = cnt ? qu[cnt - 1] : n, qu[cnt++] = i;
	}
	for (int i = 0; i < n; i++) {
		long long a = aa[i]; int c = cc[i];
		long long l = pp[i] != -1 ? aa[pp[i]] : -1;
		long long r = aa[qq[i]];
		append(0, 1, a, c);
		append(0, 1, r, -c);
		if (l != -1) {
			append(0, r - l, a, -c);
			append(0, r - l, r, c);
		}
		append(1, 1, a, -c);
		append(1, r - a, a, c);
		append(0, 1, r, c);
		append(0, r - a, r, -c);
		if (l != -1) {
			append(0, a - l + 1, a, -c);
			append(1, a - l + 1, l, c);
			append(0, r - l, r - 1, c);
			append(1, r - l, l, -c);
			append(0, r - l, a, c);
			append(0, r - l, r - 1, -c);
		}
	}
	for (int z = 0; z < 2; z++) {
		build(z, aa__[z] = compress(aa_[z], bb_[z], mm[z]));
		sort(hh[z], hh[z] + mm[z], [z] (int h0, int h1) { return dd_[z][h0] < dd_[z][h1]; });
	}
	sort(zz, zz + q, [] (int z0, int z1) { return dd[z0] < dd[z1]; });
	for (int g0 = 0, g1 = 0, y = 0; y < q; y++) {
		int z = zz[y], d = dd[z];
		for (int h; g0 < mm[0] && dd_[0][h = hh[0][g0]] <= d; g0++)
			update(0, aa_[0][h], aa__[0] - 1, cc_[0][h]);
		for (int h; g1 < mm[1] && dd_[1][h = hh[1][g1]] <= d; g1++)
			update(1, aa_[1][h], aa__[1] - 1, cc_[1][h]);
		long long l = aa[ll[z]] + d - 1, r = aa[rr[z]];
		if (l < r)
			xx[z] = calc(0, l) - calc(0, r) + calc(1, l - d) - calc(1, r - d);
	}
	sort(zz, zz + q, [] (int z0, int z1) { return ll[z0] > ll[z1]; });
	for (int cnt = 0, i = n - 1, y = 0; i >= 0; i--) {
		while (cnt && cc[i] <= cc[qu[cnt - 1]])
			cnt--;
		qu[cnt] = i, ss[cnt] = cnt ? ss[cnt - 1] + cc[i] * (aa[qu[cnt - 1]] - aa[i]) : 0, cnt++;
		for (int z; y < q && ll[z = zz[y]] == i; y++) {
			long long a = min(aa[i] + dd[z] - 1, aa[rr[z]]);
			int lower = -1, upper = cnt - 1;
			while (upper - lower > 1) {
				int h = lower + upper >> 1;
				if (aa[qu[h]] < a)
					upper = h;
				else
					lower = h;
			}
			int h = upper, j = qu[h];
			xx[z] += ss[cnt - 1] - ss[h] + cc[j] * (a - aa[j]);
		}
	}
	build(n);
	for (int z = 0; z < q; z++)
		cout << (query(ll[z], rr[z] - 1) <= dd[z] ? xx[z] : -1) << '\n';
	return 0;
}

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