Submission #1284799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284799		Faisal_Saqib	Fish 3 (JOI24_fish3)	C++20	44 / 100	2095 ms	30768 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+100;
ll c[N],pre[N],last[N],aws[N];
pair<int,int> qry[N];
vector<int> sl[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ll n,d;
    cin>>n>>d;
    ll mx_=0;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        pre[i]=pre[i-1]+c[i];
        if(c[i]==1)
        {
            last[i]=last[i-1];
        }
        else
        {
            last[i]=i;
        }
        mx_=max(mx_,c[i]);
    }
    ll q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        ll l,r;
        cin>>l>>r;
        if(d==1)
        {
            qry[i]={l,r};
            sl[r].push_back(i);
            continue;
        }
        if(mx_<=1)
        {
            ll cur=pre[r]-pre[max(l-1,last[r])];
            ll tot=pre[r]-pre[l-1];
            tot-=cur;
            if(tot==0)
            {
                cout<<0<<endl;
            }
            else
            {
                // tot>0
                if(d>1)
                {
                    cout<<-1<<endl;
                }
                else
                {
                    cout<<tot<<endl;
                }
            }
            continue;
        }
        ll ans=0,mi=c[r];
        for(int k=r;k>=l;k--)
        {
            mi=min(mi,c[k]);
            ll cur=(d-((c[k]-mi)%d))%d;
            mi-=cur;
            if(mi<0)
            {
                ans=-1;
                break;
            }
            if((c[k]-mi)%d)
            {
                ans=-1;
                break;
            }
            ans+=(c[k]-mi)/d;
        }
        cout<<ans<<endl;
    }
    if(d==1)
    {
        vector<int> st;
        c[0]=0;
        st.push_back(0);
        vector<ll> sm={0};
        for(int r=1;r<=n;r++)
        {
            while(st.size()>0 and c[st.back()]>c[r])
            {
                st.pop_back();
                sm.pop_back();
            }
            // r,r-1,r-2 .. ,st.back()+1 will have min equal to c[r]
            sm.push_back(sm.back()+c[r]*(r-st.back()));
            st.push_back(r);
            for(auto i:sl[r])
            {
                int l=qry[i].first;
                // we need to get sum for [l,r]
                // st is sorted
                // 
                auto it=lower_bound(begin(st),end(st),l)-begin(st);
                int ilr=st[it];
                // cout<<"Solving "<<i<<" query "<<l<<' '<<r<<endl;
                // cout<<"Got "<<it<<' '<<ilr<<endl;
                // cout<<"St: "<<endl;
                // for(auto x:st)cout<<x<<' ';
                // cout<<endl;
                // cout<<"SM: "<<endl;
                // for(auto x:sm)
                // {
                //     cout<<x<<' ';
                // }
                // cout<<endl;
                aws[i]=(pre[r]-pre[l-1])-(sm.back()-sm[it] + c[ilr]*(ilr-l+1));
                // l *it  r
            }
        }
        for(int i=0;i<q;i++)
        {
            cout<<aws[i]<<endl;
        }
        // cout<<endl;
    }
}

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