Submission #1105610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105610		pedroslrey	Fish 3 (JOI24_fish3)	C++14	100 / 100	612 ms	65676 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using lli = long long;

class rmq {
private:
	vector<lli> seg; int sz;

	lli query(int pos, int ini, int fim, int l, int r) {
		if (l <= ini && fim <= r) return seg[pos];
		if (r <= ini || fim <= l) return 1e18;

		int m = (ini + fim)/2;
		return min(query(2*pos, ini, m, l, r), query(2*pos + 1, m, fim, l, r));
	}

	void build(int pos, int ini, int fim, vector<lli> &xs) {
		if (ini == fim) return;
		if (ini + 1 == fim) {
			seg[pos] = xs[ini];
			return;
		}

		int m = (ini + fim)/2;
		build(2*pos, ini, m, xs);
		build(2*pos + 1, m, fim, xs);

		seg[pos] = min(seg[2*pos], seg[2*pos + 1]);
	}

public:
	rmq(vector<lli> &xs) : seg (4*xs.size() + 10), sz (xs.size()) { build(1, 0, xs.size(), xs); }

	lli query(int l, int r) { return query(1, 0, sz, l, r); }
};

class segtree {
private:
	vector<lli> seg, lazy; int sz;

	inline void refresh(int pos, int ini, int fim) {
		if (lazy[pos] == -1e18) return;
		if (ini + 1 < fim) lazy[2*pos] = lazy[2*pos + 1] = lazy[pos];

		seg[pos] = lazy[pos]*(fim - ini);
		lazy[pos] = -1e18;
	} 

	void update(int pos, int ini, int fim, int l, int r, lli x) {
		refresh(pos, ini, fim);
		if (l <= ini && fim <= r) {
			lazy[pos] = x;
			refresh(pos, ini, fim);
			return;
		}
		if (r <= ini || fim <= l) return;

		int m = (ini + fim)/2;
		update(2*pos, ini, m, l, r, x);
		update(2*pos + 1, m, fim, l, r, x);

		seg[pos] = seg[2*pos] + seg[2*pos + 1];
	}

	lli query(int pos, int ini, int fim, int l, int r) {
		refresh(pos, ini, fim);
		if (l <= ini && fim <= r) return seg[pos];
		if (r <= ini || fim <= l) return 0;

		int m = (ini + fim)/2;
		return query(2*pos, ini, m, l, r) +
			   query(2*pos + 1, m, fim, l, r);
	}

public:
	segtree(int n) : sz (n), seg (4*n + 10), lazy (4*n + 10, -1e18) { }

	void update(int l, int r, lli x) { update(1, 0, sz, l, r, x); }
	lli query(int l, int r) { return query(1, 0, sz, l, r); }
};

int main() {
	int n; lli d;
	cin >> n >> d;

	vector<lli> cs(n);
	for (lli &c: cs)
		cin >> c;

	vector<int> offset(n);
	for (int i = 1; i < n; ++i) 
		offset[i] = cs[i]%d >= cs[i - 1]%d ? offset[i-1] : offset[i-1] + 1;

	vector<lli> vals(n);
	for (int i = 0; i < n; ++i) 
		vals[i] = cs[i] - d*offset[i];

	rmq R(vals);

	int q;
	cin >> q;

	vector<vector<pair<int, int>>> queries(n);
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;

		--l; --r;

		queries[r].emplace_back(l, i);
	}

	stack<pair<lli, int>> mins;
	mins.emplace(-1e18, -1);

	vector<lli> pref(n);
	pref[0] = cs[0]/d - offset[0];
	for (int i = 1; i < n; ++i)
		pref[i] = pref[i-1] + cs[i]/d - offset[i];

	vector<lli> ans(q); segtree S(n);
	for (int i = 0; i < n; ++i) {
		lli v = cs[i]/d - offset[i];

		while (mins.top().first > v) mins.pop();

		S.update(mins.top().second + 1, i + 1, v);
		mins.emplace(v, i);

		for (auto [l, idx]: queries[i]) {
			if (R.query(l, i + 1) + d*offset[l] < 0) ans[idx] = -1;
			else ans[idx] = pref[i] - (l == 0 ? 0 : pref[l - 1]) - S.query(l, i + 1);
		}
	}

	for (lli x: ans)
		cout << x << "\n";
}

Compilation message (stderr)

Main.cpp: In constructor 'segtree::segtree(int)':
Main.cpp:40:29: warning: 'segtree::sz' will be initialized after [-Wreorder]
   40 |  vector<lli> seg, lazy; int sz;
      |                             ^~
Main.cpp:40:14: warning:   'std::vector<long long int> segtree::seg' [-Wreorder]
   40 |  vector<lli> seg, lazy; int sz;
      |              ^~~
Main.cpp:77:2: warning:   when initialized here [-Wreorder]
   77 |  segtree(int n) : sz (n), seg (4*n + 10), lazy (4*n + 10, -1e18) { }
      |  ^~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:131:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |   for (auto [l, idx]: queries[i]) {
      |             ^

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