Submission #1217975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217975		trimkus	Fish 3 (JOI24_fish3)	C++20	0 / 100	148 ms	24876 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int MAXN = 3e5;
ll d;
struct LazySeg {
	ll lz[4 * MAXN + 1];
	ll mnV[MAXN + 1], sum[MAXN + 1];
	int n;
	void init(int n) {
		this->n = n;
	}
	void push(int i, int l, int r) {
		if (lz[i] == 0) return;
		sum[i] += lz[i] * (r - l + 1);
		mnV[i] -= lz[i] * d;
		if (l < r) {
			lz[i * 2] += lz[i];
			lz[i * 2 + 1] += lz[i];
		}
		lz[i] = 0;
	}
	void combine(int i, int j, int k) {
		sum[i] = sum[j] + sum[k];
		mnV[i] = min(mnV[j], mnV[k]);
	}
	array<ll, 2> combine_query(int j, array<ll, 2> nres = {0, LLONG_MAX}) {
		array<ll, 2> res = nres;
		res[0] += sum[j];
		res[1] = min({res[1], mnV[j]});
		return res;
	}
	void turnon(int i, int l, int r, int qp, ll val) {
		push(i, l, r);
		if (l == r) {
			mnV[i] = val;
			return;
		}
		int m = (l + r) / 2;
		if (qp <= m) turnon(i * 2, l, m, qp, val);
		else turnon(i * 2 + 1, m + 1, r, qp, val);
		combine(i, i * 2, i * 2 + 1);
	}
	void turnon(int qp, ll val) {turnon(1, 1, n, qp, val);}
	void update(int i, int l, int r, int ql, int qr, ll val) {
		push(i, l, r);
		if (ql > r || l > qr) return;
		if (ql <= l && r <= qr) {
			lz[i] += val;
			push(i, l, r);
			return;
		}
		int m = (l + r) / 2;
		update(i * 2, l, m, ql, qr, val);
		update(i * 2 + 1, m + 1, r, ql, qr, val);
		combine(i, i * 2, i * 2 + 1);
	}
	void update(int ql, int qr, ll val) {update(1, 1, n, ql, qr, val);}
	array<ll, 2> query(int i, int l, int r, int ql, int qr) {
		push(i, l, r);
		if (ql <= l && r <= qr) {
			return {mnV[i], sum[i]};
		}
		array<ll, 2> res;
		int m = (l + r) / 2;
		if (ql <= m) res = combine_query(i * 2);
		if (m + 1 <= qr) res = combine_query(i * 2 + 1, res);
		return res;
	}
	ll query(int ql, int qr) {
		if (ql == qr) return 0;
		array<ll, 2> q = query(1, 1, n, ql, qr);
		if (q[1] < 0) return -1;
		return q[0];
	}
} tree;

int main() {
	//~ ofstream cout("out.txt");
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n >> d;
	tree.init(n);
	
	vector<vector<array<int, 2>>> quer(n + 1);
	vector<ll> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		quer[r].push_back({l, i});
	}
	vector<array<ll, 2>> st = {{0, (ll)1e18}};
	vector<ll> res(q);
	for (int i = 2; i <= n; ++i) {
		tree.turnon(i - 1, a[i - 1]);
		if (a[i] >= a[i - 1]) {
			st.push_back({i - 1, (a[i] - a[i - 1]) / d});
		} else {
			ll need = (a[i - 1] - a[i] + d - 1) / d;
			int pos = i;
			while (need > 0) {
				auto& [ni, have] = st.back();
				ll take = min(need, have);
				tree.update(ni + 1, pos - 1, take);
				need -= take;
				have -= take;
				if (have == 0) {
					pos = ni + 1;
					st.pop_back();
				}
			}
		}
		for (auto [l, j] : quer[i]) {
			res[j] = tree.query(l, i);
		}
	}
	for (int i = 0; i < q; ++i) {
		cout << res[i] << "\n";
	}
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36