Submission #1267926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267926		MateiKing80	Fish 3 (JOI24_fish3)	C++20	100 / 100	582 ms	53712 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
ll d;
const ll inf = 1e13;

const int N = 300005;

struct node {
	ll sum, len, mn, lazy;
};

node operator + (node a, node b) {
	return {a.sum + b.sum, a.len + b.len, min(a.mn, b.mn), inf};
}

node aint[4 * N];

void propag(int nod) {
	if (aint[nod].lazy == inf)
		return;
	aint[nod].sum = aint[nod].len * aint[nod].lazy;
	aint[nod].mn = aint[nod].lazy;
	if (aint[nod].len > 1)
		aint[2 * nod].lazy = aint[2 * nod + 1].lazy = aint[nod].lazy;
	aint[nod].lazy = inf;
}

void build (int pos, int st, int dr) {
	aint[pos] = {0, dr - st + 1, 0, inf};
	if (st == dr)
		return;
	int mid = (st + dr) / 2;
	build (2 * pos, st, mid);
	build (2 * pos + 1, mid + 1, dr);
}

void update(int pos, int st, int dr, int l, int r, ll eq) {
	propag(pos);
	if (l <= st && dr <= r) {
		aint[pos].lazy = eq;
		propag(pos);
		return;
	}
	int mid = (st + dr) / 2;
	if (l <= mid)
		update(2 * pos, st, mid, l, r, eq);
	else
		propag(2 * pos);
		
	if (mid < r)
		update(2 * pos + 1, mid + 1, dr, l, r, eq);
	else
		propag(2 * pos + 1);
		
	aint[pos] = aint[2 * pos] + aint[2 * pos + 1];
}

node query(int pos, int st, int dr, int l, int r) {
	propag(pos);
	if (l <= st && dr <= r)
		return aint[pos];
	int mid = (st + dr) / 2;
	if (r <= mid)
		return query(2 * pos, st, mid, l, r);
	else if (mid < l)
		return query(2 * pos + 1, mid + 1, dr, l, r);
	return query(2 * pos, st, mid, l, r) + query(2 * pos + 1, mid + 1, dr, l, r);
}

struct QRY {
	int l, r, pos;
};

signed main() {
	int n;
	cin >> n >> d;
	vector<ll> v(n);
	for (int i = 0; i < n; i ++) {
		ll c;
		cin >> c;
		v[i] = c;
	}
	auto nv = v;
	ll scazi = 0;
	for (int i = 0; i < n; i ++) {
		nv[i] -= scazi;
		scazi += (nv[i] % d + d) % d;
		nv[i] -= (nv[i] % d + d) % d;
		nv[i] /= d;
		v[i] /= d;
	}
	build(1, 0, n - 1);
	vector<ll> sp(n);
	sp[0] = nv[0];
	for (int i = 1; i < n; i ++)
		sp[i] = sp[i - 1] + nv[i];
	int q;
	cin >> q;
	vector<QRY> vq;
	for (int i = 0; i < q; i ++) {
		int l, r;
		cin >> l >> r;
		vq.push_back({l - 1, r - 1, i});
	}
	sort(vq.begin(), vq.end(), [&](QRY a, QRY b) {return a.r < b.r;});
	vector<ll> ans(q);
	stack<int> skyline;
	vector<int> prev(n);
	for (int i = n - 1; i >= 0; i --) {
		while (!skyline.empty() && nv[skyline.top()] > nv[i]) {
			prev[skyline.top()] = i + 1;
			skyline.pop();
		}
		skyline.push(i);
	}
	while (!skyline.empty()) {
		prev[skyline.top()] = 0;
		skyline.pop();
	}
	int p = 0;
	for (int i = 0; i < n; i ++) {
		update(1, 0, n - 1, prev[i], i, nv[i]);
		while (p < (int)vq.size() && vq[p].r == i) {
			auto x = query(1, 0, n - 1, vq[p].l, vq[p].r);
			if (x.mn + v[vq[p].l] - nv[vq[p].l] < 0)
				ans[vq[p].pos] = -1;
			else
				ans[vq[p].pos] = sp[vq[p].r] - (vq[p].l == 0 ? 0 : sp[vq[p].l - 1]) - x.sum;
			p ++;
		}
	}
	for (int i = 0; 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