Submission #1286047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286047		kaiboy	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	1822 ms	118812 KiB

Main

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

using namespace std;

const int  N = 200000;
const int  Q = 200000;
const int M0 = N * 10;
const int M1 = N * 4;
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 dd0[M0], aa0[M0], bb0[M0]; int cc0[M0], hh0[M0];
long long dd1[M1], aa1[M1], bb1[M1]; int cc1[M1], hh1[M1];
long long st0[M_ << 1], lz0[M_], sz0[M_ << 1]; int h0_, n0_;
long long st1[M_ << 1], lz1[M_], sz1[M_ << 1]; int h1_, n1_;
long long ss[N];
int st_[N_ << 1], n_;

int compress(long long *aa, long long *bb, int n) {
	static int ii[M0];
	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 put0(int i, long long a) {
	st0[i] += a * sz0[i];
	if (i < n0_)
		lz0[i] += a;
}

void pus0(int i) {
	if (lz0[i]) {
		int l = i << 1, r = l ^ 1;
		put0(l, lz0[i]);
		put0(r, lz0[i]);
		lz0[i] = 0;
	}
}

void pul0(int i) {
	if (!lz0[i]) {
		int l = i << 1, r = l ^ 1;
		st0[i] = st0[l] + st0[r];
	}
}

void push0(int i) {
	for (int h = h0_; h; h--)
		pus0(i >> h);
}

void pull0(int i) {
	while (i >>= 1)
		pul0(i);
}

void build0(int n) {
	h0_ = 0, n0_ = 1;
	while (n0_ < n)
		h0_++, n0_ <<= 1;
	for (int i = 0; i + 1 < n; i++)
		sz0[i + n0_] = bb0[i + 1] - bb0[i];
	for (int i = n0_ - 1; i; i--) {
		int l = i << 1, r = l ^ 1;
		sz0[i] = sz0[l] + sz0[r];
	}
}

void update0(int l, int r, int a) {
	int l_ = l += n0_, r_ = r += n0_;
	push0(l_), push0(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put0(l++, a);
		if (!(r & 1))
			put0(r--, a);
	}
	pull0(l_), pull0(r_);
}

long long query0(int l, int r) {
	long long a = 0;
	push0(l += n0_), push0(r += n0_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			a += st0[l++];
		if (!(r & 1))
			a += st0[r--];
	}
	return a;
}

long long calc0(long long a, int n) {
	int lower = -1, upper = n;
	while (upper - lower > 1) {
		int i = lower + upper >> 1;
		if (bb0[i] >= a)
			upper = i;
		else
			lower = i;
	}
	int i = upper;
	long long x = 0;
	if (i < n) {
		x += query0(i, n - 1);
		if (i)
			x += query0(i - 1, i - 1) / (bb0[i] - bb0[i - 1]) * (bb0[i] - a);
	}
	return x;
}

void put1(int i, long long a) {
	st1[i] += a * sz1[i];
	if (i < n1_)
		lz1[i] += a;
}

void pus1(int i) {
	if (lz1[i]) {
		int l = i << 1, r = l ^ 1;
		put1(l, lz1[i]);
		put1(r, lz1[i]);
		lz1[i] = 0;
	}
}

void pul1(int i) {
	if (!lz1[i]) {
		int l = i << 1, r = l ^ 1;
		st1[i] = st1[l] + st1[r];
	}
}

void push1(int i) {
	for (int h = h1_; h; h--)
		pus1(i >> h);
}

void pull1(int i) {
	while (i >>= 1)
		pul1(i);
}

void build1(int n) {
	h1_ = 0, n1_ = 1;
	while (n1_ < n)
		h1_++, n1_ <<= 1;
	for (int i = 0; i + 1 < n; i++)
		sz1[i + n1_] = bb1[i + 1] - bb1[i];
	for (int i = n1_ - 1; i; i--) {
		int l = i << 1, r = l ^ 1;
		sz1[i] = sz1[l] + sz1[r];
	}
}

void update1(int l, int r, int a) {
	int l_ = l += n1_, r_ = r += n1_;
	push1(l_), push1(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put1(l++, a);
		if (!(r & 1))
			put1(r--, a);
	}
	pull1(l_), pull1(r_);
}

long long query1(int l, int r) {
	long long a = 0;
	push1(l += n1_), push1(r += n1_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			a += st1[l++];
		if (!(r & 1))
			a += st1[r--];
	}
	return a;
}

long long calc1(long long a, int n) {
	int lower = -1, upper = n;
	while (upper - lower > 1) {
		int i = lower + upper >> 1;
		if (bb1[i] >= a)
			upper = i;
		else
			lower = i;
	}
	int i = upper;
	long long x = 0;
	if (i < n) {
		x += query1(i, n - 1);
		if (i)
			x += query1(i - 1, i - 1) / (bb1[i] - bb1[i - 1]) * (bb1[i] - a);
	}
	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;
	}
	int m0 = 0, m1 = 0;
	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]];
		dd0[m0] = 1, aa0[m0] = a, cc0[m0] = c, hh0[m0] = m0, m0++;
		dd0[m0] = 1, aa0[m0] = r, cc0[m0] = -c, hh0[m0] = m0, m0++;
		if (l != -1) {
			dd0[m0] = r - l, aa0[m0] = a, cc0[m0] = -c, hh0[m0] = m0, m0++;
			dd0[m0] = r - l, aa0[m0] = r, cc0[m0] = c, hh0[m0] = m0, m0++;
		}
		dd1[m1] = 1, aa1[m1] = a, cc1[m1] = -c, hh1[m1] = m1, m1++;
		dd1[m1] = r - a, aa1[m1] = a, cc1[m1] = c, hh1[m1] = m1, m1++;
		dd0[m0] = 1, aa0[m0] = r, cc0[m0] = c, hh0[m0] = m0, m0++;
		dd0[m0] = r - a, aa0[m0] = r, cc0[m0] = -c, hh0[m0] = m0, m0++;
		if (l != -1) {
			dd0[m0] = a - l + 1, aa0[m0] = a, cc0[m0] = -c, hh0[m0] = m0, m0++;
			dd1[m1] = a - l + 1, aa1[m1] = l, cc1[m1] = c, hh1[m1] = m1, m1++;
			dd0[m0] = r - l, aa0[m0] = r - 1, cc0[m0] = c, hh0[m0] = m0, m0++;
			dd1[m1] = r - l, aa1[m1] = l, cc1[m1] = -c, hh1[m1] = m1, m1++;
			dd0[m0] = r - l, aa0[m0] = a, cc0[m0] = c, hh0[m0] = m0, m0++;
			dd0[m0] = r - l, aa0[m0] = r - 1, cc0[m0] = -c, hh0[m0] = m0, m0++;
		}
	}
	int a0 = compress(aa0, bb0, m0); build0(a0);
	sort(hh0, hh0 + m0, [] (int h0, int h1) { return dd0[h0] < dd0[h1]; });
	int a1 = compress(aa1, bb1, m1); build1(a1);
	sort(hh1, hh1 + m1, [] (int h0, int h1) { return dd1[h0] < dd1[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 < m0 && dd0[h = hh0[g0]] <= d; g0++)
			update0(aa0[h], a0 - 1, cc0[h]);
		for (int h; g1 < m1 && dd1[h = hh1[g1]] <= d; g1++)
			update1(aa1[h], a1 - 1, cc1[h]);
		long long l = aa[ll[z]] + d - 1, r = aa[rr[z]];
		if (l < r)
			xx[z] = calc0(l, a0) - calc0(r, a0) + calc1(l - d, a1) - calc1(r - d, a1);
	}
	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