Submission #1205965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205965		duckindog	Fish 3 (JOI24_fish3)	C++17	27 / 100	304 ms	48640 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 300'000 + 10,
		  	MAX = 1'000'000'000'000;
int n, d, q;
int c[N];
vector<pair<int, int>> save[N];

namespace IT { 
	int f[N << 2], lazy[N << 2];

	void update(int id, int l, int r, int u, int v, int x) { 
		if (v < l || r < u) return;
		if (u <= l && r <= v) { 
			f[id] += x;
			lazy[id] += x;
			return;
		}
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, u, v, x);
		update(id << 1 | 1, mid + 1, r, u, v, x);
		f[id] = min(f[id << 1], f[id << 1 | 1]) + lazy[id];
	}
	int query(int id, int l, int r, int u, int v) { 
		if (v < l || r < u) return MAX;
		if (u <= l && r <= v) return f[id];
		int mid = (l + r) >> 1;
		return min(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v)) + lazy[id];
	}
}

vector<int> pos;
int dif[N], isErr[N];
int pref[N], prefA[N], prefB[N];

int answer[N];

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

	cin >> n >> d;
	for (int i = 1; i <= n; ++i) cin >> c[i];
	cin >> q;
	for (int i = 1; i <= q; ++i) { 
		int l, r; cin >> l >> r;
		save[r].push_back({l, i});
	}

	pos = {1};
	for (int i = 1; i < n; ++i) { 
		if (c[i] >= c[i + 1]) { 
			dif[i] = (c[i] > c[i + 1] ? (c[i] - c[i + 1] - 1) / d + 1 : 0);

			if (c[i] < dif[i] * d) isErr[i] = true;
			
			pref[i] = pref[i - 1] + dif[i];
			prefA[i] = prefA[i - 1] + dif[i] * (i - pos.back() + 1);

			prefB[pos.size()] += dif[i] * (i - pos.back() + 1);
		} else {
			pref[i] = pref[i - 1];
			prefA[i] = prefA[i - 1];

			pos.push_back(i + 1);
			prefB[pos.size()] = prefB[pos.size() - 1];
		}
	} 
	pref[n] = pref[n - 1];
	prefA[n] = prefA[n - 1];

	auto cal = [&](int l, int r) { 
		int idL = upper_bound(pos.begin(), pos.end(), l) - pos.begin() - 1,
			idR = upper_bound(pos.begin(), pos.end(), r) - pos.begin() - 1;
		if (idL == idR) { 
			return prefA[r] - prefA[l - 1] - (pref[r] - pref[l - 1]) * (l - pos[idL]);
		}
		int edL = pos[idL + 1] - 1, stR = pos[idR];

		int ret = prefB[idR] - prefB[idL + 1];
		ret += prefA[edL] - prefA[l - 1] - (pref[edL] - pref[l - 1]) * (l - pos[idL]);
		ret += prefA[r] - prefA[stR - 1];
		
		return ret;
	};
	
	for (int i = 1; i <= n; ++i) { 
		IT::update(1, 1, n, i, i, c[i] / d);
	}
	for (int i = 2, it = 1; i <= n; ++i) { 
		int last = *(upper_bound(pos.begin(), pos.end(), i) - 1);
		IT::update(1, 1, n, last, i - 1, -dif[i - 1]);

		if (isErr[i - 1]) it = i;
		for (; it < i; ++it) { 
			if (IT::query(1, 1, n, it, i - 1) >= 0) break;
		}

		for (const auto& [l, id] : save[i]) { 
			if (l < it) { answer[id] = -1; continue; }
			if (l == i) { answer[id] = 0; continue; }

			answer[id] = cal(l, i - 1);
		}
	}

	for (int i = 1; i <= q; ++i) cout << answer[i] << "\n";
}

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