제출 #1285622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285622		kaiboy	Dungeon 3 (JOI21_ho_t5)	C++20	14 / 100	207 ms	27156 KiB

Main

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

using namespace std;

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

long long aa[N + 1]; int cc[N + 1];
int ll[Q], rr[Q], zz[Q]; long long xx[Q];
long long bb[N << 1]; int ii[N << 1];
int pq[N], iq[N + 1], pq_cnt;
long long aa_[N << 1], pp[N << 1]; int cc_[N << 1];
int qu[N]; long long qq[N];
int st[N_ << 1], n_;

bool lt(int i, int j) {
	return cc[i] < cc[j];
}

int p2(int p) {
	return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p + 1], iq[p]));
}

void pq_up(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++pq_cnt, pq_up(i);
}

void pq_remove(int i) {
	int j = iq[pq_cnt--];
	if (i != j)
		pq[j] = pq[i], pq_up(j), pq_dn(j);
	pq[i] = 0;
}

long long calc(long long a, int m) {
	int lower = -1, upper = m;
	while (upper - lower > 1) {
		int h = lower + upper >> 1;
		if (a <= aa_[h])
			upper = h;
		else
			lower = h;
	}
	int h = upper;
	if (h == m)
		return -1;
	if (!h)
		return cc_[h] * a;
	return pp[h - 1] + cc_[h] * (a - aa_[h - 1]);
}

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];
	int d;
	for (int z = 0; z < q; z++)
		cin >> ll[z] >> rr[z] >> d, ll[z]--, rr[z]--, zz[z] = z;
	for (int i = 0; i < n << 1; i++)
		bb[ii[i] = i] = aa[i >> 1] + (i & 1 ? d : 0);
	sort(ii, ii + (n << 1), [] (int i, int j) { return bb[i] < bb[j]; });
	int m = 0;
	for (int h = 0; h < n << 1; ) {
		long long a = bb[ii[h]];
		aa_[m] = a, cc_[m] = pq_cnt ? cc[iq[1]] : -1, m++;
		for ( ; h < n << 1 && bb[ii[h]] == a; h++) {
			int i = ii[h] >> 1;
			if (!pq[i])
				pq_add(i);
			else
				pq_remove(i);
		}
	}
	pp[0] = cc_[0] * aa_[0];
	for (int h = 1; h < m; h++)
		pp[h] = pp[h - 1] + cc_[h] * (aa_[h] - aa_[h - 1]);
	for (int z = 0; z < q; z++) {
		long long l = aa[ll[z]], r = aa[rr[z]];
		if (l + d <= r)
			xx[z] = calc(r, m) - calc(l + d - 1, m);
	}
	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, qq[cnt] = cnt ? qq[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] + d - 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] += qq[cnt - 1] - qq[h] + cc[j] * (a - aa[j]);
		}
	}
	build(n);
	for (int z = 0; z < q; z++)
		cout << (query(ll[z], rr[z] - 1) <= d ? xx[z] : -1) << '\n';
	return 0;
}

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