Submission #1264633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264633		jbareja	Dungeon 3 (JOI21_ho_t5)	C++20	11 / 100	4094 ms	11328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
#define rep(i, p, k) for (int i(p); i<(k); i++)
#define per(i, p, k) for (int i(p); i>(k); i--)
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define NODEBUG if constexpr(!dbg)
#define DC DEBUG cerr

struct SegTreeSum {
	vector<ll> values;
	int base = 1;
	ll NEUTRAL = 0;

	void Init(vector<int>& vec) {
		int n = sz(vec);
		while (base <= n) base *= 2;
		values.assign(base * 2, NEUTRAL);
		rep(i, 0, n) values[base + i] = vec[i];
		per(i, base-1, 0) values[i] = values[i*2] + values[i*2+1];
	}

	ll Sum(int l, int r) {
		if (r < l) return NEUTRAL;
		l += base - 1;
		r += base + 1;
		ll ans = NEUTRAL;
		while (l/2 != r/2) {
			if (l % 2 == 0) ans += values[l+1];
			if (r % 2 != 0) ans += values[r-1];
			l /= 2, r /= 2;
		}
		return ans;
	}
};

struct SegTreeMax {
	vector<int> values;
	int base = 1;
	int NEUTRAL = INT_MIN;

	void Init(vector<int>& vec) {
		int n = sz(vec);
		while (base <= n) base *= 2;
		values.assign(base * 2, NEUTRAL);
		rep(i, 0, n) values[base + i] = vec[i];
		per(i, base-1, 0) values[i] = max(values[i*2], values[i*2+1]);
	}

	int Max(int l, int r) {
		l += base - 1;
		r += base + 1;
		int ans = NEUTRAL;
		while (l/2 != r/2) {
			if (l % 2 == 0) ans = max(ans, values[l+1]);
			if (r % 2 != 0) ans = max(ans, values[r-1]);
			l /= 2, r /= 2;
		}
		return ans;
	}
};

struct SegTreeMin {
	vector<PII> values;
	int base = 1;
	PII NEUTRAL = { INT_MAX, -1 };

	PII Merge(PII a, PII b) {
		return min(a, b);
	}

	void Init(vector<int>& vec) {
		int n = sz(vec);
		while (base <= n) base *= 2;
		values.assign(base * 2, NEUTRAL);
		rep(i, 0, n) values[base + i] = { vec[i], i };
		per(i, base-1, 0) values[i] = min(values[i*2], values[i*2+1]);
	}

	PII Min(int l, int r) {
		// DC << "Min(" << l << "," << r << ") = ";
		l += base - 1;
		r += base + 1;
		PII ans = NEUTRAL;
		while (l/2 != r/2) {
			if (l % 2 == 0) ans = Merge(ans, values[l+1]);
			if (r % 2 != 0) ans = Merge(ans, values[r-1]);
			l /= 2, r /= 2;
		}
		// DC << "(" << ans.st << "," << ans.nd << ")\n";
		return ans;
	}
};

struct SegTreeLinearFunction {
	vector<PII> values;
	int base = 1;
	PII NEUTRAL = { 0, 0 };

	PII Merge(PII a, PII b) {
		return { a.st + b.st, a.nd + b.nd };
	}

	void Init(int n) {
		while (base <= n) base *= 2;
		values.assign(base * 2, NEUTRAL);
	}

	void Set(int i, int a, int b) {
		i += base;
		values[i] = { a, b };
		while (i / 2) {
			i /= 2;
			values[i] = Merge(values[i*2], values[i*2+1]);
		}
	}

	PII Sum(int l, int r) {
		l += base - 1;
		r += base + 1;
		PII ans = NEUTRAL;
		while (l/2 != r/2) {
			if (l % 2 == 0) ans = Merge(ans, values[l+1]);
			if (r % 2 != 0) ans = Merge(ans, values[r-1]);
			l /= 2, r /= 2;
		}
		return ans;
	}
};

int n; // liczba odcinków między stacjami
int q; // liczba zapytań

vector<int> A; // A[i] - odległość między stacjami i oraz i+1
vector<int> B; // B[i] - cena paliw na i-tej stacji (nie ma ceny n+1 stacji)

SegTreeMax tree_max_dist;
SegTreeMin tree_min_cost;
vector<ll> pref; // pref[i] - dystans od 1 do i

vector<int> dl; // dl[i] - najbliższa tańsza stacja po lewej (indeks)
vector<int> dr; // dr[i] - najbliższa tańsza stacja po prawej (indeks)

void calculate_dl() {
	stack<PII> S; // < wartość, indeks >
	rep(i, 1, n+1) {
		while (!S.empty() && S.top().st >= B[i]) S.pop();
		if (sz(S)) dl[i] = S.top().nd;
		else dl[i] = INT_MAX;
		S.push({B[i], i});
	}
	S = {};
	DEBUG {
		// cerr << '\n';
		// rep(i, 1, n+1) DC << B[i] << ' ';
		// cerr << '\n';
		// rep(i, 1, n+1) {
		// 	if (dl[i] != INT_MAX) cerr << dl[i] << ' ';
		// 	else cerr << "- ";
		// }
		// cerr << '\n';
	}
}

void calculate_dr() {
	stack<PII> S; // < wartość, indeks >
	per(i, n, 0) {
		while (!S.empty() && S.top().st >= B[i]) S.pop();
		if (sz(S)) dr[i] = S.top().nd;
		else dr[i] = INT_MAX;
		S.push({B[i], i});
	}
	S = {};
	DEBUG {
		// cerr << '\n';
		// rep(i, 1, n+1) DC << B[i] << ' ';
		// cerr << '\n';
		// rep(i, 1, n+1) {
		// 	if (dr[i] != INT_MAX) cerr << dr[i] << ' ';
		// 	else cerr << "- ";
		// }
		// cerr << '\n';
	}
}

ll dist(int l, int r) {
	if (r <= l) return 0;
	return pref[r] - pref[l];
}

ll answer(int l, int r, ll u) {
	ll ans = 0;
	int i = l;
	ll u_now = 0;
	while (i < r) {
		DC << "\n=> jestem w " << i << ", u_now = " << u_now << '\n';
		int low = i+1, high = r;
		while (low < high) {
			int mid = (low + high + 1) / 2;
			if (dist(i, mid) <= u) low = mid;
			else high = mid-1;
		}
		int j = low;

		DC << "najdalej mogę dojechać do " << j << " dist = " << dist(i, j) << '\n';
		int k = dr[i];
		DC << "następna tańsza stacja jest w " << k << "\n";
		if (k > j) {
			if (j == r) {
				DC << "kupuję " << (dist(i,j) - u_now) << " za " << (dist(i,j) - u_now) * B[i] << '\n';
				ll temp = dist(i,j);
				ans += (temp - u_now) * B[i];
				u_now = temp;
			}
			else {
				DC << "kupuję " << (u - u_now) << " za " << (u - u_now) * B[i] << '\n';
				ans += (u - u_now) * B[i];
				u_now = u;
			}
		}
		else {
			ll temp = dist(i, k);
			if (temp > u_now) {
				DC << "kupuję " << (dist(i,k) - u_now) << " za " << (dist(i,k) - u_now) * B[i] << '\n';
				ans += (temp - u_now) * B[i];
				u_now = temp;
			}
		}
		u_now -= A[i];
		i++;
	}
	return ans;
}

int main() {
	NODEBUG { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

	cin >> n >> q;
	A.assign(n+1, 0);
	B.assign(n+1, 0);
	dr.assign(n+1, 0);
	dl.assign(n+1, 0);
	pref.assign(n+7, 0);
	rep(i, 1, n+1) {
		cin >> A[i];
		pref[i+1] = A[i] + pref[i];
	}
	rep(i, 1, n+1) cin >> B[i];
	tree_max_dist.Init(A);
	tree_min_cost.Init(B);

	// calculate_dl();
	calculate_dr();

	rep(i, 0, q) {
		int l, r; ll u;
		cin >> l >> r >> u;

		if (tree_max_dist.Max(l, r-1) > u) {
			cout << "-1\n";
			continue;
		}

		cout << answer(l, r, u) << '\n';
	}
}

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