Submission #1268026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268026		Boomyday	Fish 3 (JOI24_fish3)	C++20	100 / 100	766 ms	55120 KiB

Main

//
// Created by adavy on 9/7/2025.
//
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int ssz = 524288;

vector<ll> seg(2*ssz, 0);
vector<ll> smin(2*ssz, -1);
vector<ll> lz(2*ssz, -1);

// range set range sum

void pushdown(int rt, int tl, int tr){
    if (lz[rt] != -1){
        seg[rt] = lz[rt] * (tr - tl + 1);
        smin[rt] = lz[rt];
        if (tl != tr){
            lz[rt*2] = lz[rt];
            lz[rt*2+1] = lz[rt];
        }
        lz[rt] = -1;
    }
}

void add(ll x, int l, int r, int rt, int tl, int tr){
    pushdown(rt, tl, tr);
    if (tr < l || r < tl) return;
    if (l <= tl && tr <= r){
        lz[rt] = x;
        pushdown(rt, tl, tr);
        return;
    }
    int mid = (tl + tr) / 2;
    add(x, l, r, rt*2, tl, mid);
    add(x, l, r, rt*2+1, mid+1, tr);
    seg[rt] = seg[rt*2] + seg[rt*2+1];
    smin[rt] = max(smin[rt*2], smin[rt*2+1]);
}

ll sum(int l, int r, int rt, int tl, int tr){
    pushdown(rt, tl, tr);
    if (tr < l || r < tl) return 0;
    if (l <= tl && tr <= r) return seg[rt];
    int mid = (tl + tr) / 2;
    return sum(l, r, rt*2, tl, mid) + sum(l, r, rt*2+1, mid+1, tr);
}

void find_split(int& split, ll sval, int rlim, int rt, int tl, int tr){
    pushdown(rt, tl, tr);
    if (tl == tr){
        if (smin[rt] > sval) split = min(split, tl);
        return;
    }
    int tm = (tl + tr) / 2;
    if ( rlim < tm){
        find_split(split, sval,rlim, rt*2, tl, tm);
        return;
    }
    pushdown(rt*2, tl, tm);
    if(smin[rt*2] > sval){
        split = min(split, tm);
        find_split(split, sval, rlim, rt*2, tl, tm);
    } else {
        find_split(split, sval, rlim, rt*2+1, tm+1, tr);
    }

}


int main(){
    int N; ll D;
    cin >> N >> D;
    vector<ll> h(N);
    for(int i=0;i<N;++i) cin >> h[i];
    vector<ll> d(N);

    vector<ll> hprefs(N+1,0), dprefs(N+1,0);
    d[N-1] = 0;
    for(int i=N-1;i>=0;--i) {
        d[i] = d[i+1] + (((h[i+1]-h[i])%D + D)%D);
    }
    // output d
    //for (auto&x:d) cout << x << " ";
    //cout << endl;
    for(int i=0;i<N;++i){
        hprefs[i+1] = hprefs[i] + h[i];
        dprefs[i+1] = dprefs[i] + d[i];
    }

    vector<vector<pair<int,int>>>quers(N);

    // left point, index


    int Q; cin >> Q;
    vector<ll> anses(Q, -1);

    for(int i=0;i<Q;++i){
        int l, r; cin >> l >> r; l--; r--;
        quers[r].push_back( {l, i});
    }
    for(int r=0;r<N;++r){
        // find the split point and update
        // the split point is the first point in [0, r-1] more than h[i] + d[i]
        ll sval = h[r] + d[r];
        int split = r;
        find_split(split, sval, r-1, 1, 0, ssz-1);
        //cout << "r " << r << " split " << split << endl;
        add(h[r]+d[r], split, r, 1, 0, ssz-1);
        // now compute sums
        for(auto q:quers[r]){
            int l = q.first; int ind = q.second;
            //cout << "lr " << l << " " << r << endl;
            if (sum(l, l, 1, 0, ssz-1) < d[l]) {
                anses[ind] = -1;
            }
            else {
                anses[ind] = ((hprefs[r+1]-hprefs[l])-(sum(l, r, 1, 0, ssz-1) - (dprefs[r+1]-dprefs[l])))/D;
            }
        }
    }
    for(auto&a:anses) cout << a << endl;
}

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