Submission #1162301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162301		irmuun	Fish 3 (JOI24_fish3)	C++20	27 / 100	322 ms	43936 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct lazySeg{
	ll n;
	vector<ll>d,lazy;
	lazySeg(ll n){
		d.resize(4*n);
		lazy.resize(4*n);
	}
	void push(ll v,ll l,ll r){
		ll mid=(l+r)>>1;
		d[v<<1]+=lazy[v]*(mid-l+1);
		lazy[v<<1]+=lazy[v];
		d[v<<1|1]+=lazy[v]*(r-mid);
		lazy[v<<1|1]+=lazy[v];
		lazy[v]=0;
	}
	ll query(ll v,ll l,ll r,ll L,ll R){
		if(R<L||r<L||R<l) return 0ll;
		if(L<=l&&r<=R){
			return d[v];
		}
		push(v,l,r);
		ll mid=(l+r)>>1;
		return query(v<<1,l,mid,L,R)+query(v<<1|1,mid+1,r,L,R);
	}
	void update(ll v,ll l,ll r,ll L,ll R,ll val){
		if(R<L||r<L||R<l) return;
		if(L<=l&&r<=R){
			d[v]+=(r-l+1)*val;
			lazy[v]+=val;
			return;
		}
		push(v,l,r);
		ll mid=(l+r)>>1;
		update(v<<1,l,mid,L,R,val);
		update(v<<1|1,mid+1,r,L,R,val);
		d[v]=d[v<<1]+d[v<<1|1];
	}
};

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	ll n,d;
	cin>>n>>d;
	ll c[n+5];
	for(ll i=1;i<=n;i++){
		cin>>c[i];
	}
	ll q;
	cin>>q;
	vector<pair<ll,ll>>ask[n+5];
	vector<ll>ans(q);
	for(ll i=0;i<q;i++){
		ll l,r;
		cin>>l>>r;
		ask[r].pb({l,i});
	}
	lazySeg sg(n);
	vector<pair<ll,ll>>block;
	for(ll R=1;R<=n;R++){
		if(block.empty()||c[R-1]+d<=c[R]){
			block.pb({R,R});
		}
		else{
			if(c[R-1]<=c[R]){
				block.back().ss++;
			}
			else{
				ll need=(c[R-1]-c[R]+d-1)/d;
				{
					ll l=block.back().ff,r=block.back().ss;
					sg.update(1,1,n,l,r,need);
				}
				while(block.size()>=2){
					ll l=block[block.size()-2].ff,r=block[block.size()-2].ss;
					{
						ll x=c[r]-sg.query(1,1,n,r,r)*d,y=c[r+1]-sg.query(1,1,n,r+1,r+1)*d;
						if(x+d<=y){
							break;
						}
						else{
							if(x<=y){
								block[block.size()-2].ss=block.back().ss;
								block.pop_back();
								break;
							}
							else{
								ll cnt=(x-y+d-1)/d;
								sg.update(1,1,n,block.back().ff,block.back().ss,cnt);
								block[block.size()-2].ss=block.back().ss;
								block.pop_back();
							}
						}
					}
				}
				block.back().ss=R;
			}
		}
		for(auto [L,i]:ask[R]){
			if(c[L]-sg.query(1,1,n,L,L)*d<0){
				ans[i]=-1;
			}
			else{
				ans[i]=sg.query(1,1,n,L,R);
			}
		}
	}
	for(ll i=0;i<q;i++){
		cout<<ans[i]<<"\n";
	}
}

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