Submission #1136710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136710		NK_	Fish 3 (JOI24_fish3)	C++20	100 / 100	559 ms	56440 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 = 1e13 + 1008;
ll SUM[2 * nax], MN[2 * nax], lzy[2 * nax];

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] != INF) {
		SUM[x] = lzy[x] * 1LL * (R - L + 1);
		MN[x] = lzy[x];

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

	lzy[x] = INF;
}

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);
}

ll sum(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l) return 0LL;
	if (l <= L && R <= r) return SUM[x];

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

ll mn(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l) return INF;
	if (l <= L && R <= r) return MN[x];

	int M = (L + R) / 2;
	return min(mn(l, r, 2 * x, L, M), mn(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] = INF;
	}
	
	int N; ll K; cin >> N >> K;

	vl C(N); for(auto& x : C) cin >> x;

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

	vi R(N, 0);
	vl D(N), A(N); 

	for(int i = 0; i < N; i++) {
		D[i] = C[i] / K;
		C[i] %= K;

		if (i) {
			R[i] = R[i - 1];
			if (C[i] < C[i - 1]) R[i]++;
		}

		A[i] = D[i] - R[i];
		// cout << i << " -> " << A[i] << " " << C[i] << " " << D[i] << " " << R[i] << endl;
	}

	vl P = {0};
	for(auto& x : A) P.pb(P.back() + x);

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

	vi stk = {-1}; vl ans(Q, -1);
	for(int r = 0; r < N; r++) {
		while(stk.back() != -1 && A[stk.back()] > A[r]) stk.pop_back();

		// cout << stk.back() + 1 << " " << r << " " << A[r] << endl;

		upd(stk.back() + 1, r, A[r]);
		stk.pb(r);

		for(auto& [l, i] : QRY[r]) {
			// ll S = qry(l, r);
			// ll s = sum(l, r);
			// cout << l << " " << r << " " << i << " ---> " << S << " " << s << endl;

			// cout << mn(l, r) << " <-> " << R[l] << endl;
			if ((mn(l, r) + R[l]) >= 0) ans[i] = qry(l, r) - sum(l, r);
		}

	}

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

	exit(0-0);
}	

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