Submission #1218376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218376		trimkus	Fish 3 (JOI24_fish3)	C++20	28 / 100	304 ms	54288 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int MAXN = 3e5;
ll d;

struct LazySeg {
	vector<ll> tree;
	vector<ll> lz;
	vector<ll> sum;
	int n;
	LazySeg(int n) {
		this->n = n;
		tree = vector<ll>(4 * n, LLONG_MAX);
		lz = vector<ll>(4 * n, LLONG_MAX);
		sum = vector<ll>(4 * n);
	}
	void upd(int i, int l, int r, ll val) {
		tree[i] = min(tree[i], val);
		lz[i] = min(lz[i], val);
		sum[i] = tree[i] * (r - l + 1);
	}
	void push(int i, int l, int r) {
		if (lz[i] == LLONG_MAX) return;
		if (l < r) {
			int m = (l + r) / 2;
			upd(i * 2, l, m, lz[i]);
			upd(i * 2 + 1, m + 1, r, lz[i]);
		}
		lz[i] = LLONG_MAX;
	}
	void update(int i, int l, int r, int ql, int qr, ll val) {
		if (l > qr || r < ql) return;
		if (ql <= l && r <= qr) {
			tree[i] = val;
			lz[i] = val;
			sum[i] = val * (r - l + 1);
			return;
		}
		push(i, l, r);
		int m = (l + r) / 2;
		update(i * 2, l, m, ql, qr, val);
		update(i * 2 + 1, m + 1, r, ql, qr, val);
		sum[i] = sum[i * 2] + sum[i * 2 + 1];
	}
	void update(int ql, int qr, ll val) {
		update(1, 1, n, ql, qr, val);
	}
	ll query(int i, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return 0;
		if (ql <= l && r <= qr) {
			return sum[i];
		}
		push(i, l, r);
		int m = (l + r) / 2;
		return 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;
	cin >> n >> d;
	LazySeg tree(n);
	vector<ll> a(n + 1);
	vector<ll> ps(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		ps[i] = a[i] + ps[i - 1];
	}
	deque<pair<ll, int>> dq;
	dq.push_back({-1, 0});
	int q;
	cin >> q;
	vector<vector<pair<int, int>>> quer(n + 1);
	vector<ll> res(q);
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		quer[r].push_back({l, i});
	}
	for (int i = 1; i <= n; ++i) {
		while (dq.size() && dq.back().first >= a[i]) dq.pop_back();
		assert(dq.size() > 0);
		int ql = dq.back().second + 1;
		dq.push_back({a[i], i});
		tree.update(ql, i, a[i]);
		//~ cerr << ql << " " << i << " = " << a[i] << "\n";
		//~ cerr << "\n";
		for (auto& [l, j] : quer[i]) {
			//~ cerr << "Query = " << l << " " << i << " = " << tree.query(l, i) << "\n";
			res[j] = ps[i] - ps[l - 1] - tree.query(l, i);
		}
	}
	for (auto& u : res) {
		cout << u << "\n";
	}
}

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