Submission #1007590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007590		batsukh2006	Fish 3 (JOI24_fish3)	C++17	100 / 100	277 ms	128488 KiB

Main

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
 
using namespace std;
 
#define MOD 1000000007
#define int long long
#define endl '\n'
#define ff first
#define ss second
typedef pair<int,int> pp;
void solve(){
    int n,d; cin>>n>>d;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++) cin>>a[i];
    vector<int> dp(n+1),pref(n+2),comp(n+1);
    dp[n]=a[n];
    for(int i=n-1; i>=1; i--){
        if(a[i]>dp[i+1]){
            comp[i]=((a[i]-dp[i+1])+(d-1))/d;
            dp[i]=a[i]-((a[i]-dp[i+1])+(d-1))/d*d;
            pref[i]=pref[i+1]+((a[i]-dp[i+1])+(d-1))/d;
        }else{
            comp[i]=0;
            dp[i]=a[i];
            pref[i]=pref[i+1];
        }
    }
    stack<int> s;
    s.push(0);
    vector<vector<pp> > p(n+1,vector<pp>(20));
    for(int i=1; i<=n; i++){
        while(s.size()>1&&comp[s.top()]>=comp[i]) s.pop();
        p[i][0]=make_pair(s.top(),comp[i]*(i-s.top()));
        s.push(i);
    }
    for(int i=1; i<20; i++){
        for(int j=1; j<=n; j++){
            p[j][i].ff=p[p[j][i-1].ff][i-1].ff;
            p[j][i].ss=p[j][i-1].ss+p[p[j][i-1].ff][i-1].ss;
        }
    }
    int q; cin>>q;
    while(q--){
        int l,r; cin>>l>>r;
        int cur=r,sum=0;
        int ans=pref[l]-pref[r+1];
        for(int i=19; i>=0; i--){
            if(p[cur][i].ff>=l){
                sum+=p[cur][i].ss;
                cur=p[cur][i].ff;
            }
        }
        sum+=comp[cur]*(cur-l+1);
        if(dp[l]+comp[cur]*d<0) cout<<-1<<endl;
        else cout<<ans-sum<<endl;
    }
}
signed main(){
	// freopen("hps.in", "r", stdin);
	// freopen("hps.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int t=1;
	// cin>>t;
	while(t--){
		solve();
		cout<<endl;
	}
	return 0;
}

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