Submission #998703

#	Time	Username	Problem	Language	Result	Execution time	Memory
998703		tosivanmak	Fish 3 (JOI24_fish3)	C++17	100 / 100	617 ms	189508 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll lg[300005];
struct ST{
  vector<vector<ll> >st;
  vector<ll>arr;
    void init(ll n){
        arr.resize(n+5),st.resize(n+5);
        for(int i=0;i<n+5;i++){
            st[i].resize(21);
        }
    }
    void build(ll n){
        for(int i=1;i<=n;i++){
            st[i][0]=arr[i];
        }
        for(int j=1;j<=20;j++){
             for(int i=1;i<=n;i++){
                 if(i+(1<<(j-1))<=n){
                     st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
                 }
             }   
        }
    }
    ll qry(ll ql, ll qr){
        ll rng=lg[qr-ql+1];
        return min(st[ql][rng],st[qr-(1<<rng)+1][rng]);
    }
}st;
stack<pair<ll,ll> >s;
pair<ll,ll>jmp[300005][21];
ll psum[300005],arr[300005],a[300005],c[300005];
ll n,d;
ll qry(ll ql, ll qr){
    ll ans=0;
    ll redu=a[ql];
    ll real=c[ql]%d;
    ll add=redu-real;
    ll mini=st.qry(ql,qr)+add;
    // cout<<st.qry(ql,qr)<<' ';
    if(mini<0)return -1;
    for(int i=20;i>=0;i--){
        if(jmp[qr][i].first>=ql){
            ans+=jmp[qr][i].second;
            qr=jmp[qr][i].first;
        }
    }
    ans+=(psum[qr]-psum[ql-1]-(qr-ql+1)*arr[qr])/d;
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>d;
    for(int i=2;i<=300000;i*=2)lg[i]=1;
    for(int i=3;i<=300000;i++)lg[i]+=lg[i-1];
    for(int i=1;i<=n;i++){
       cin>>c[i];
    }
    st.init(n);
    for(int i=1;i<=n;i++){
        ll prev=c[i-1]%d,cur=c[i]%d;
        if(cur>=prev){
            a[i]=a[i-1]+cur-prev;
        }
        else{
            a[i]=a[i-1]+cur-prev+d;
        }
    }
    for(int i=1;i<=n;i++){
        arr[i]=c[i]-a[i];
        // cout<<arr[i]<<" ";
        psum[i]=psum[i-1]+arr[i];
        st.arr[i]=arr[i];
    }
    st.build(n);
    for(int i=n;i>=1;i--){
        while(s.size()){
            if(arr[i]<s.top().first){
                jmp[s.top().second][0]={i,(psum[s.top().second]-psum[i]-s.top().first*(s.top().second-i))/d};
                s.pop();
            }
            else{
                break;
            }
        }
        s.push({arr[i],i});
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            ll nxt=jmp[i][j-1].first;
            jmp[i][j]={jmp[nxt][j-1].first,jmp[i][j-1].second+jmp[nxt][j-1].second};
        }
    }
    ll q;
    cin>>q;
    while(q--){
        ll l,r;
        cin>>l>>r;
        cout<<qry(l,r)<<'\n';
    }
}

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