제출 #1267913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267913		MateiKing80	Fish 3 (JOI24_fish3)	C++20	9 / 100	2094 ms	5664 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
ll d;
const ll inf = 1e18;

signed main() {
	int n;
	cin >> n >> d;
	vector<ll> v(n);
	for (int i = 0; i < n; i ++) {
		ll c;
		cin >> c;
		v[i] = c;
	}
	auto nv = v;
	ll scazi = 0;
	for (int i = 0; i < n; i ++) {
		nv[i] -= scazi;
		scazi += (nv[i] % d + d) % d;
		nv[i] -= (nv[i] % d + d) % d;
		nv[i] /= d;
		v[i] /= d;
	}
	int q;
	cin >> q;
	while (q --) {
		int l, r;
		cin >> l >> r;
		l --, r --;
		ll minnSuf = inf, ans = 0;
		for (int i = r; i >= l; i --) {
			minnSuf = min(minnSuf, nv[i]);
			ans += nv[i] - minnSuf;
		}
		if (minnSuf + v[l] - nv[l] < 0)
			cout << -1 << '\n';
		else
			cout << ans << '\n';
	}
}

/*

algoritmul de optimizat este astfel: 
le faci pe toate cu operatii de tip 1 sa fie 0 modulo d
daca e vreuna negativa atunci nu se poate
imparti totul la d sa fie mai usor
raspunsul este suma tuturor - suma(i : l..r)(min dupa i)

ca sa aflii daca nu se poate poti sa %d la inceput pe toate, apoi un rmq si aflii daca minimul este <= ceva 
hai ca bag brutul sa vad exact cum arata
*/

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