Submission #1286314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286314		kaiboy	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	1131 ms	103204 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 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 ft[2][M], ft_[2][M];
long long ss[N];
int st_[N_ << 1], n__;

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

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 update(long long *ft, int i, int n, long long a) {
	for ( ; i < n; i |= i + 1)
		ft[i] += a;
}

long long query(long long *ft, int i) {
	long long a = 0;
	for ( ; i >= 0; i &= i + 1, i--)
		a += ft[i];
	return a;
}

long long calc(int z, long long b) {
	int a_ = aa__[z], lower = -1, upper = a_;
	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 < a_) {
		x += query(ft[z], a_ - 1 - a);
		if (a)
			x += query(ft_[z], a - 1) * (bb_[z][a_ - 1] - 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++) {
		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++) {
			int a = aa_[0][h], a_ = aa__[0], c = cc_[0][h];
			update(ft[0], a_ - 1 - a, a_, c * (bb_[0][a_ - 1] - bb_[0][a]));
			update(ft_[0], a, a_, c);
		}
		for (int h; g1 < mm[1] && dd_[1][h = hh[1][g1]] <= d; g1++) {
			int a = aa_[1][h], a_ = aa__[1], c = cc_[1][h];
			update(ft[1], a_ - 1 - a, a_, c * (bb_[1][a_ - 1] - bb_[1][a]));
			update(ft_[1], a, a_, c);
		}
		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