제출 #1220481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220481		trimkus	Fish 3 (JOI24_fish3)	C++20	100 / 100	346 ms	54704 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int MAXN = 3e5;
ll d;
const ll INF = 4e18;
struct LazySeg {
	int n;
	struct Node {
		ll sumD, mnH, lz;
		Node() {
			sumD = mnH = lz = 0;
		}
		Node friend operator + (const Node& lhs, const Node& rhs) {
			Node res;
			res.sumD = lhs.sumD + rhs.sumD;
			res.mnH = min(lhs.mnH, rhs.mnH);
			return res;
		}
	};
	
	Node tree[4 * MAXN + 1];
	void init(int n) {
		this->n = n;
		for (int i = 0; i <= 4 * MAXN; ++i) {
			tree[i].mnH = INF;
		}
	}
	void push(int i, int l, int r) {
		if (tree[i].lz == 0) {
			return;
		}
		tree[i].sumD += tree[i].lz * (r - l + 1);
		tree[i].mnH -= d * tree[i].lz;
		if (l < r) {
			tree[i * 2].lz += tree[i].lz;
			tree[i * 2 + 1].lz += tree[i].lz;
		}
		tree[i].lz = 0;
	}
	void activate(int i, int l, int r, int qp, ll val) {
		//~ cerr << "at index = " << i << " , with bounds = [" << l << " , " << r << "]\n";
		push(i, l, r);
		if (qp > r || l > qp) return;
		if (l == r) {
			tree[i].mnH = val;
			return;
		}
		int m = (l + r) / 2;
		activate(i * 2, l, m, qp, val);
		activate(i * 2 + 1, m + 1, r, qp, val);
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
	void activate(int qp, ll val) {
		activate(1, 1, n - 1, qp, val);
	}
	void update(int i, int l, int r, int ql, int qr, ll val) {
		push(i, l, r);
		if (l > qr || ql > r) return;
		if (ql <= l && r <= qr) {
			tree[i].lz = 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);
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
	void update(int ql, int qr, ll val) {
		update(1, 1, n - 1, ql, qr, val);
	}
	Node query(int i, int l, int r, int ql, int qr) {
		push(i, l, r);
		if (ql <= l && r <= qr) {
			return tree[i];
		}
		int m = (l + r) / 2;
		Node res;
		if (ql <= m) res = query(i * 2, l, m, ql, qr);
		if (m + 1 <= qr) res = res + query(i * 2 + 1, m + 1, r, ql, qr);
		return res;
	}
	ll query(int l, int r) {
		if (l == r) return 0;
		Node res = query(1, 1, n - 1, l, r - 1);
		if (res.mnH < 0) return -1;
		return res.sumD;
	}
	
} seg;

int main() {
	//~ ofstream cout("out.txt");
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n >> d;
	seg.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<pair<int, ll>> left = {{0, INF}};
	vector<ll> res(q);
	for (int i = 2; i <= n; ++i) {
		//~ cerr << i << "\n";
		seg.activate(i - 1, a[i - 1]);
		//~ cerr << "activated at = " << i - 1 << "\n";
		if (a[i] >= a[i - 1]) {
			left.push_back({i - 1, (a[i] - a[i - 1]) / d}); 
		} else {
			ll need = (a[i - 1] - a[i] + d - 1) / d;
			int r = i;
			//~ cerr << "Need to update at = " << r << ", need = " << need << "\n";
			while (need > 0) {
				auto& [l, have] = left.back();
				ll take = min(need, have);
				seg.update(l + 1, r - 1, need);
				need -= take;
				have -= take;
				//~ cerr << "update at [" << l + 1 << " , " << r - 1 << "], we still need = " << need << "\n";
				if (have == 0) {
					r = l + 1;
					left.pop_back();
				}
			}
		}
		for (auto [l, idx] : quer[i]) {
			res[idx] = seg.query(l, i);
		}
	}
	cerr << "Queries = \n";
	for (auto& i : res) {
		cout << i << "\n";
	}
}

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