Submission #984788

#	Time	Username	Problem	Language	Result	Execution time	Memory
984788		pavement	Fish 3 (JOI24_fish3)	C++17	100 / 100	551 ms	82700 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define pb push_back
#define eb emplace_back

int N, Q, suf[300005];
ll D, C[300005], ans[300005], pre[300005];
vector<int> limiters;
vector<ii> vec[300005];
multiset<int> inv;

struct node {
	node *left, *right;
	int S, E;
	ll val, pv;
	bool ip;
	node(int _s, int _e) : S(_s), E(_e), val(0), ip(0){
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void prop() {
		if (!ip) {
			return;
		}
		left->val = (left->E - left->S + 1) * pv;
		right->val = (right->E - right->S + 1) * pv;
		left->pv = right->pv = pv;
		left->ip = right->ip = 1;
		ip = 0;
	}
	void upd(int l, int r, ll v) {
		if (l > E || r < S) {
			return;
		}
		if (l <= S && E <= r) {
			val = (E - S + 1) * v;
			pv = v;
			ip = 1;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = left->val + right->val;
	}
	ll qry(int l, int r) {
		if (l > E || r < S) {
			return 0;
		}
		if (l <= S && E <= r) {
			return val;
		}
		prop();
		return left->qry(l, r) + right->qry(l, r);
	}
} *root;

int find_inv(int l, int r) {
	int lo = l, hi = r, ans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (C[r] / D - (suf[mid] - suf[r]) < 0) {
			ans = mid;
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> D;
	for (int i = 1; i <= N; i++) {
		cin >> C[i];
	}
	for (int i = N - 1; i >= 1; i--) {
		suf[i] = suf[i + 1] + (C[i + 1] % D < C[i] % D);
	}
	for (int i = 1; i <= N; i++) {
		pre[i] = pre[i - 1] + (C[i] / D + suf[i]);
	}
	cin >> Q;
	for (int i = 1, L, R; i <= Q; i++) {
		cin >> L >> R;
		vec[R].eb(L, i);
	}
	root = new node(1, N);
	for (int R = 1; R <= N; R++) {
		while (!limiters.empty()) {
			int x = limiters.back();
			auto a = (C[R] / D) - (suf[x + 1] - suf[R]);
			auto b = C[x + 1] % D;
			if (a * D + b <= C[x]) {
				limiters.pop_back();
				int y = (limiters.empty() ? 0 : limiters.back()) + 1;
				inv.erase(inv.find(find_inv(y, x)));
			} else {
				break;
			}
		}
		int y = (limiters.empty() ? 0 : limiters.back()) + 1;
		limiters.pb(R);
		root->upd(y, R, C[R] / D + suf[R]);
		int tmp = find_inv(y, R);
		inv.insert(tmp);
		for (auto [L, idx] : vec[R]) {
			if (*inv.rbegin() >= L) {
				ans[idx] = -1;
			} else {
				ans[idx] = pre[R] - pre[L - 1] - root->qry(L, R);
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << ans[i] << '\n';
	}
}

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