Submission #1172217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172217		ByeWorld	Fish 3 (JOI24_fish3)	C++20	100 / 100	500 ms	52536 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int MAXN = 3e5+10;
const int INF = 1e9;
const int SQRT = 500;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, d, ans[MAXN], a[MAXN], pr[MAXN];
vector <pii> que[MAXN];

struct seg {
	int st[4*MAXN], mn[4*MAXN], laz[4*MAXN];
	void bd(int id, int l, int r){
		if(l==r){ st[id] = a[l]; mn[id] = a[l]; return; }
		bd(lf,l,md); bd(rg,md+1,r);
		st[id] = st[lf]+st[rg];
		mn[id] = min(mn[lf], mn[rg]);
	}
	void bnc(int id,int l,int r){
		if(laz[id]==0) return;
		st[lf] += laz[id] * (md-l+1); mn[lf] += laz[id]; laz[lf] += laz[id];
		st[rg] += laz[id] * (r-md); mn[rg] += laz[id]; laz[rg] += laz[id];
		laz[id] = 0;
	}
	int que(int id,int l,int r,int x,int y){
		if(r<x || y<l) return 0;
		if(x<=l && r<=y) return st[id];
		bnc(id,l,r);
		return que(lf,l,md,x,y)+que(rg,md+1,r,x,y);
	}
	int MN(int id,int l,int r,int x,int y){
		if(r<x || y<l) return INF;
		if(x<=l && r<=y) return mn[id];
		bnc(id,l,r);
		return min(MN(lf,l,md,x,y), MN(rg,md+1,r,x,y));
	}
	void upd(int id,int l,int r,int x,int y,int p){
		if(r<x || y<l) return;
		if(x<=l && r<=y){
			laz[id] += p; st[id] += p * (r-l+1);
			mn[id] += p;
			return;
		}
		bnc(id,l,r);
		upd(lf,l,md,x,y,p); upd(rg,md+1,r,x,y,p);
		st[id] = st[lf]+st[rg]; mn[id] = min(mn[lf], mn[rg]);
		return;
	}
} A;

signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>d;
	for(int i=1; i<=n; i++){
		cin>>a[i]; pr[i] = pr[i-1]+a[i];
	}
	A.bd(1,1,n);
	int q; cin>>q;
	for(int i=1; i<=q; i++){
		int l, r; cin>>l>>r;
		que[r].pb({l,i});
	}

	vector<pii> st; st.pb({-INF, 0});
	for(int i=1; i<=n; i++){
		int L = i, valnw = a[i];
		while(st.back().fi > valnw){
			int c = (st.back().fi-valnw+d-1)/d;
			A.upd(1,1,n,st.back().se,L-1,-c*d);

			L = st.back().se;
			valnw = A.que(1,1,n,L,L);
			st.pop_back();
		}
		st.pb({a[i], L}); // i gabung

		for(auto [l,id] : que[i]){
			ans[id] = A.que(1,1,n,l,i);
			if(A.MN(1,1,n,l,i) < 0) ans[id] = -1;
			else {
				ans[id] = ((pr[i]-pr[l-1])-ans[id])/d;
			}
		}
	}
	for(int i=1; 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