Submission #1012398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012398		12345678	Fish 3 (JOI24_fish3)	C++17	100 / 100	382 ms	57476 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e5+5;

ll n, d, c[nx], q, l[nx], r[nx], res[nx], t[nx], sv[nx];
vector<ll> qrs[nx];
stack<pair<ll, ll>> st;

struct segtree
{
    ll d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i]*(r-l+1);
        if (l==r) return lz[i]=0, void();
        lz[2*i]+=lz[i];
        lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md ,2*i, ql, qr, vl);
        update(md+1, r ,2*i+1, ql, qr, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        if (l==r) cout<<l<<' '<<r<<' '<<d[i]<<'\n';
        if (l==r) return;
        int md=(l+r)/2;
        show(l, md ,2*i);
        show(md+1, r, 2*i+1);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>d;
    for (int i=1; i<=n; i++) cin>>c[i];
    for (int i=1; i<n; i++) 
    {
        if (c[i]>c[i+1]) t[i]=(c[i]-c[i+1])/d+((c[i]-c[i+1])%d!=0);
    }
    for (int i=1; i<n; i++) if (c[i]<c[i+1]) sv[i]=(c[i+1]-c[i])/d;
    cin>>q;
    for (int i=1; i<=q; i++) cin>>l[i]>>r[i], qrs[r[i]].push_back(i);
    st.push({LLONG_MAX, 0});
    for (int i=1; i<=n; i++)
    {
        for (auto x:qrs[i]) 
        {
            if (s.query(1, n, 1, l[x], l[x])*d>c[l[x]]) res[x]=-1;
            else res[x]=s.query(1, n, 1, l[x], r[x]-1);
        }
        if (t[i])
        {
            while (t[i]>0)
            {
                auto tmp=st.top();
                st.pop();
                if (tmp.first<=t[i])
                {
                    t[i]-=tmp.first;
                    s.update(1, n, 1, tmp.second+1, i, tmp.first);
                }
                else
                {
                    tmp.first-=t[i];
                    s.update(1,n, 1, tmp.second+1, i, t[i]);
                    t[i]=0;
                    st.push(tmp);
                }
            }
        }
        if (sv[i])
        {
            st.push({sv[i], i});
        }
    }
    for (int i=1; i<=q; i++) cout<<res[i]<<'\n';
}

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