Submission #991789

#	Time	Username	Problem	Language	Result	Execution time	Memory
991789		CodePlatina	Fish 3 (JOI24_fish3)	C++17	100 / 100	525 ms	52584 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
const int INF = (int)1e9 + 7;

using namespace std;

vector<pii> qr[303030];

ll seg[1212121];
ll lazy[1212121];

void down(int ind, int s, int e, ll x)
{
	seg[ind] += x * (e - s);
	lazy[ind] += x;
}

void prop(int ind, int s, int e)
{
	if(lazy[ind])
	{
		int mid = s + e >> 1;
		down(ind << 1, s, mid, lazy[ind]);
		down(ind << 1 | 1, mid, e, lazy[ind]);
		lazy[ind] = 0;
	}
}

void upd(int ind, int s, int e, int l, int r, ll x)
{
	if(r <= s || e <= l) return;
	if(l <= s && e <= r)
	{
		down(ind, s, e, x);
		return;
	}

	prop(ind, s, e);
	int mid = s + e >> 1;
	upd(ind << 1, s, mid, l, r, x);
	upd(ind << 1 | 1, mid, e, l, r, x);
	seg[ind] = seg[ind << 1] + seg[ind << 1 | 1];
}

ll qry(int ind, int s, int e, int l, int r)
{
	if(r <= s || e <= l) return 0;
	if(l <= s && e <= r) return seg[ind];

	prop(ind, s, e);
	int mid = s + e >> 1;
	return qry(ind << 1, s, mid, l, r) + qry(ind << 1 | 1, mid, e, l, r);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; ll d; cin >> n >> d;
	ll A[n]; for(auto &i : A) cin >> i;
	int T; cin >> T;
	for(int i = 0; i < T; ++i)
	{
		int l, r; cin >> l >> r; --l;
		qr[r].push_back({l, i});
	}

	ll ps[n + 1]; ps[0] = 0;
	for(int i = 0; i < n; ++i) ps[i + 1] = ps[i] + A[i];

	vector<int> V;
	ll ans[T];
	for(int r = 1; r <= n; ++r)
	{
		upd(1, 0, n, r - 1, r, A[r - 1]);
		V.push_back(r - 1);
		while(V.size() >= 2)
		{
			ll x = qry(1, 0, n, V.back() - 1, V.back());
			ll y = qry(1, 0, n, V.back(), V.back() + 1);
			if(x <= y) break;
			ll t = ((x - y - 1) / d + 1) * d;
			upd(1, 0, n, V[(int)V.size() - 2], V.back(), -t);
			V.pop_back();
		}
		for(auto [l, i] : qr[r])
		{
			if(qry(1, 0, n, l, l + 1) < 0) ans[i] = -1;
			else ans[i] = (ps[r] - ps[l] - qry(1, 0, n, l, r)) / d;
		}


		// for(int i = 0; i < n; ++i) cout << qry(1, 0, n, i, i + 1) << ' '; cout << endl;
	}

	for(int i = 0; i < T; ++i) cout << ans[i] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void prop(int, int, int)':
Main.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid = s + e >> 1;
      |             ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int, ll)':
Main.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In function 'll qry(int, int, int, int, int)':
Main.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid = s + e >> 1;
      |            ~~^~~

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