제출 #1136711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136711		NK_	Fish 3 (JOI24_fish3)	C++20	20 / 100	564 ms	53752 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using vi = V<int>;
using vl = V<ll>;

const int nax = (1 << 19);
const ll INF = 1e18 + 1008;
ll sum[2 * nax], mn[2 * nax], lzy[2 * nax];

AR<ll, 2> cmb(AR<ll, 2> a, AR<ll, 2> b) { return AR<ll, 2>{a[0] + b[0], min(a[1], b[1])}; }

void pull(int x) { 
	sum[x] = sum[2 * x] + sum[2 * x + 1]; 
	mn[x] = min(mn[2 * x], mn[2 * x + 1]);
}

void push(int x, int L, int R) {
	if (lzy[x]) {
		sum[x] += (R - L + 1) * 1LL * lzy[x];
		mn[x] += lzy[x];

		if (L != R) for(int i = 0; i < 2; i++) {
			lzy[2 * x + i] += lzy[x];
		}
	}

	lzy[x] = 0;
}

void upd(int l, int r, ll v, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l) return;
	if (l <= L && R <= r) {
		lzy[x] += v; push(x, L, R); return;
	}

	int M = (L + R) / 2;
	upd(l, r, v, 2 * x, L, M);
	upd(l, r, v, 2 * x + 1, M + 1, R);
	pull(x);
}

AR<ll, 2> qry(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l) return AR<ll, 2>{0, INF};
	if (l <= L && R <= r) return AR<ll, 2>{sum[x], mn[x]};

	int M = (L + R) / 2;
	return cmb(qry(l, r, 2 * x, L, M), qry(l, r, 2 * x + 1, M + 1, R));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	

	for(int i = 0; i < 2 * nax; i++) {
		sum[i] = 0;
		mn[i] = 0;
		lzy[i] = 0;
	}

	int N; ll D; cin >> N >> D;

	vl c(N), C(N); for(auto& x : C) cin >> x;
	// vl P = {0};
	vl d(N); vi prv(N, -2); for(int i = 0; i < N; i++) {

		if (i && C[i] > C[i - 1]) prv[i] = prv[i - 1];
		else prv[i] = i - 1;

		d[i] = C[i] / D;
		upd(i, i, d[i]);
		c[i] = C[i] % D;

		// P.pb(P.back() + d[i]);
	}

	// for(auto& x : prv) cout << x << " ";	
	// cout << endl;

	// auto query = [&](int l, int r) { return P[r + 1] - P[l]; };

	for(int i = 1; i < nax; i++) pull(i);

	V<V<AR<int, 2>>> QRY(N);
	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int l, r; cin >> l >> r; --l, --r;
		QRY[l].pb(AR<int, 2>{r, i});
	}

	vl ans(Q);
	for(int l = N - 1; l >= 0; l--) {
		if (l + 1 < N && c[l] > c[l + 1]) {
			// cout << l + 1 << " " << N - 1 << " " << -1 << endl;
			upd(l + 1, N - 1, -1);
		}

		// for(int i = l; i < N; i++) {
		// 	auto [s, mn] = qry(i, i);
		// 	// cout << i << " -> " << s << " " << mn << endl;
		// }

		for(auto& [r, i] : QRY[l]) {
			ll mn = qry(l, r)[1];
			r = max(l - 1, prv[r]);
			ll s = qry(l, r)[0];
			// cout << l << " " << r << " => " << s << " " << mn << endl;
			if (mn < 0) ans[i] = -1;
			else {
				ans[i] = max(0LL, s - mn * (r - l + 1));
			}
		}
	}

	for(auto& x : ans) cout << x << nl;

	exit(0-0);
}

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