Submission #1217928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217928		trimkus	Fish 3 (JOI24_fish3)	C++20	0 / 100	244 ms	17736 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;

struct RMQ {
	int n;
	vector<ll> tree;
	RMQ(int n) {
		this->n = n;
		tree = vector<ll>(4 * n);
	}
	void update(int i, int l, int r, int qp, ll val) {
		if (l == r) {
			tree[i] = val;
			return;
		}
		int m = (l + r) / 2;
		if (qp <= m) update(i * 2, l, m, qp, val);
		else update(i * 2 + 1, m + 1, r, qp, val);
		tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
	}
	void update(int qp, ll val) {
		update(1, 1, n, qp, val);
	}
	ll query(int i, int l, int r, int ql, int qr) {
		if (ql > r || l > qr) return LLONG_MAX;
		if (ql <= l && r <= qr) return tree[i];
		int m = (l + r) / 2;
		return min(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
	}
	ll query(int ql, int qr) {
		return query(1, 1, n, ql, qr);
	}
};

int main() {
	//~ ofstream cout("out.txt");
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	ll d;
	cin >> n >> d;
	vector<ll> a(n + 1);
	vector<ll> ps(n + 1);
	RMQ mn(n);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		ps[i] += a[i];
		if (i) ps[i] += ps[i - 1];
		mn.update(i, a[i]); 
	}
	vector<int> left(n + 1, -1);
	deque<int> dq;
	for (int i = 1; i <= n; ++i) {
		if (dq.size() && dq.back() > a[i]) while (dq.size()) dq.pop_back();
		dq.push_back(a[i]);
		left[i] = dq.size();
	}
	//~ for (int i = 1; i <= n; ++i) {
		//~ cout << a[i] << " ";
	//~ }
	//~ cout << "\n";
	//~ for (int i = 1; i <= n; ++i) {
		//~ cout << left[i] << " ";
	//~ }
	//~ cout << "\n";
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (r - left[r] < l) {
			cout << "0\n";
			continue;
		}
		int i = r - left[r];
		ll reduce = mn.query(l, r);
		ll take = ps[i] - ps[l - 1] - reduce * (i - l + 1);
		cout << take << "\n";
	}
}

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