Submission #1136702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136702		NK_	Fish 3 (JOI24_fish3)	C++20	7 / 100	391 ms	46096 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 seg[2 * nax], lzy[2 * nax];

void pull(int x) {
	seg[x] = seg[2 * x] + seg[2 * x + 1];
}

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

		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, int 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 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 0LL;
	if (l <= L && R <= r) return seg[x];

	int M = (L + R) / 2;
	return 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++) {
		seg[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);
	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 query = [&](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 = query(l, r);
			ll s = qry(l, r);
			// cout << l << " " << r << " " << i << " ---> " << S << " " << s << endl;

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

	}

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

	exit(0-0);
}	

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