제출 #1012397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012397		12345678	Fish 3 (JOI24_fish3)	C++17	20 / 100	191 ms	33572 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], t[nx], qs[nx];
stack<pair<ll, ll>> st;
vector<ll> qrs[nx];

struct segtree
{
    ll d[4*nx];
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md ,2*i, idx ,vl);
        update(md+1, r ,2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        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);
    }
} 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++) qs[i]=qs[i-1]+t[i];
    for (int i=1; i<n; i++) s.update(1, n, 1, i, t[i]*i);
    cin>>q;
    for (int i=1; i<=q; i++)
    {
        cin>>l[i]>>r[i];
        if ((qs[r[i]-1]-qs[l[i]-1])*d>c[l[i]]) cout<<-1<<'\n';
        else
        {
            if (l[i]==r[i]) cout<<0<<'\n';
            else cout<<s.query(1, n, 1, l[i], r[i]-1)-(l[i]-1)*(qs[r[i]-1]-qs[l[i]-1])<<'\n';
        }
    }
}

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