Submission #1179573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179573		Nonoze	Fish 3 (JOI24_fish3)	C++20	9 / 100	2094 ms	7488 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)

void solve();

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}


int n, k, q;
vector<int> a;

void solve() {
	cin >> n >> k;
	a.resize(n); for (auto &u: a) cin >> u;
	cin >> q;
	while (q--) {
		int l, r; cin >> l >> r; l--, r--;
		auto base=a;
		int nb=0, ans=0, left=0;
		for (int i=l; i<=r; i++) {
			if (a[i]<nb) { ans=-1; break; }
			nb+=(a[i]-nb)%k;
			a[i]-=nb;
			ans+=a[i]/k;
		}
		int mini=r;
		vector<int> nxt(n);
		for (int i=r; i>=l; i--) {
			if (a[i]<a[mini]) mini=i;
			nxt[i]=mini;
		}
		nb=0;
		for (int i=l; i<=r; i++) {
			if (a[nxt[i]]-nb) {
				ans-=((a[nxt[i]]-nb)/k)*(r-i+1);
				nb=a[nxt[i]];
				i=nxt[i];
			}
		}
		cmax(ans, -1LL);
		cout << ans << endl;
		a=base;
	}
}

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