제출 #1219752

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

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int MAXN = 3e5;
ll d;

int main() {
	//~ ofstream cout("out.txt");
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n >> d;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<ll> v(n);
	for (int i = n - 2; i >= 0; --i) {
		if (a[i + 1] <= a[i]) {
			v[i] = v[i + 1] + (a[i] - a[i + 1] + d - 1) / d;
		} else {
			v[i] = v[i + 1] - (a[i + 1] - a[i]) / d;
		}
	}
	vector<ll> ps(n + 1);
	for (int i = 0; i < n; ++i) {
		ps[i + 1] = ps[i] + v[i];
	}
	vector<pair<int, ll>> st = {{-1, 0}};
	int q;
	cin >> q;
	vector<ll> res(q);
	vector<vector<array<int, 2>>> quer(n);
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		quer[r].push_back({l, i});
	}
	//~ for (int i = 0; i < n + 1; ++i) {
		//~ cout << ps[i] << " ";
	//~ }
	//~ cout << "\n";
	//~ for (int i = 0; i < n + 1; ++i) {
		//~ cout << v[i] << " ";
	//~ }
	//~ cout << "\n";
	const ll INF = 1e18;
	for (int i = 0; i < n; ++i) {
		while ((int)st.size() > 1 && v[st.back().first] >= v[i]) st.pop_back();
		st.push_back({i, st.back().second + v[i] * (i - st.back().first)});
		for (auto [l, qidx] : quer[i]) {
			int idx = lower_bound(begin(st), end(st), make_pair(l, -INF)) - begin(st);
			res[qidx] = st.back().second - st[idx - 1].second - v[st[idx].first] * (l - 1 - st[idx - 1].first);
			res[qidx] = ps[i + 1] - ps[l] - res[qidx];
			if (a[l] < d * (v[l] - v[st[idx].first])) res[qidx] = -1;
		}
	}
	for (auto& u : res) {
		cout << u << "\n";
	}
}

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