Submission #1180210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180210		Alish	Fish 3 (JOI24_fish3)	C++20	100 / 100	1103 ms	44964 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;

const int N = 3e5+23;

ll c[N], ans[N], seg[4*N], lpz[4*N];
vector<pii> in[N];
ll d;
int n, q;
vector<pair<pll, pll> > st; // Mnc, Mxc, l, r

void Shift(int l, int r, int ind){
    if(r-l==1) return;
    if(!lpz[ind]) return;
    int mid=(r+l)>>1;
    seg[2*ind+1]+=(mid-l)*lpz[ind];
    lpz[2*ind+1]+=lpz[ind];

    seg[2*ind+2]+=(r-mid)*lpz[ind];
    lpz[2*ind+2]+=lpz[ind];

    lpz[ind]=0;
}

void upd(int lx, int rx, ll x, int l=1, int r=n+1, int ind=0){
    Shift(l, r, ind);
    if(lx>=r || rx<=l) return;
    if(lx<=l && rx>=r){
        seg[ind]+=x*(r-l);
        lpz[ind]+=x;
        return;
    }
    int mid=(r+l)>>1;
    upd(lx, rx, x, l, mid, 2*ind+1); upd(lx, rx, x, mid, r, 2*ind+2);
    seg[ind]=seg[2*ind+1]+seg[2*ind+2];
}

ll get(int lx, int rx, int l=1, int r=n+1, int ind=0){
    Shift(l, r, ind);
    if(lx>=r || rx<=l) return 0;
    if(lx<=l && rx>=r) return seg[ind];
    int mid=(r+l)>>1;
    return get(lx, rx, l, mid, 2*ind+1)+get(lx, rx, mid, r, 2*ind+2);
}

int main()
{
    cin>>n>>d;
    for (int i=1; i<=n; i++) cin>>c[i];

    cin>>q;
    for(int i=0; i<q; i++){
        int l, r; cin>>l>>r;
        in[r].pb({l, i});
    }

    for (int i=1; i<=n; i++){

        while(!st.empty() && st.back().F.S>c[i]){
            ll Mnc=st.back().F.F, Mxc=st.back().F.S, l=st.back().S.F, r=st.back().S.S;
            st.pop_back();
            ll x=(Mxc-c[i]+d-1)/d;
            if(!st.empty()) x=min(x, (Mnc-st.back().F.S)/d);
            upd(l, r+1, x);
            Mnc-=x*d; Mxc-=x*d;
            if(!st.empty() && Mnc-st.back().F.S<d) {
                Mnc=st.back().F.F;
                l=st.back().S.F;
                st.pop_back();
            }
            st.pb({{Mnc, Mxc}, {l, r}});
        }
        st.pb({{c[i], c[i]}, {i, i}});
        for (auto pp: in[i]){
            if(c[pp.F]-get(pp.F, pp.F+1)*d<0) ans[pp.S]=-1;
            else ans[pp.S]=get(pp.F, i+1);
        }
    }
    for (int i=0; i<q; i++) cout<<ans[i]<<endl;

}

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