Submission #1128582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128582		fzyzzz_z	Fish 3 (JOI24_fish3)	C++20	20 / 100	409 ms	23008 KiB

Main

#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

const int N = 524288; 

ll t[2 * N]; 
ll t2[2 * N]; 
void build() {
    for (int i = N - 1; i >= 1; --i) {
        t[i] = min(t[2 * i], t[2 * i + 1]); 
        t2[i] = max(t2[2 * i], t2[2 * i + 1]); 
    }
}
ll query(int L, int R, int ind = 1, int l = 0, int r = N - 1) {
    if (L <= l && r <= R) return t[ind]; 
    if (L > r || l > R) return (1LL << 60); 

    int md = (l + r) / 2; 
    return min(query(L, R, 2 * ind, l, md), query(L, R, 2 * ind + 1, md + 1, r)); 
}
ll query2(int L, int R, int ind = 1, int l = 0, int r = N - 1) {
    if (L <= l && r <= R) return t2[ind]; 
    if (L > r || l > R) return 0LL; 

    int md = (l + r) / 2; 
    return max(query2(L, R, 2 * ind, l, md), query2(L, R, 2 * ind + 1, md + 1, r)); 
}
int32_t main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 

    int n; 
    ll d; 
    cin >> n >> d; 
    vector<ll> oc(n); 
    for (auto & x: oc) {
        cin >> x; 
    }

    vector<ll> p(n, 0); 
    ll last = (1LL << 60); 
    for (int i = n - 1; i >= 0; --i) {
        if (oc[i] <= last) {
            last = oc[i]; 
        } else {
            p[i] = ((oc[i] - last) + d - 1) / d; 
            last = oc[i] - p[i] * d; 
        }
        ll nd = max(0LL, -last); 
        t2[i + N] = (nd + d - 1) / d; 
        // cout << "!!! " << last << ' ' << p[i] << ' ' << t2[i + N] << '\n'; 
        assert(t2[i + N] <= p[i]); 
    }
    for (int i = 0; i < n; ++i) {
        t[i + N] = p[i]; 
        if (i) p[i] += p[i - 1]; 
    }
    build(); 
    auto get = [&] (int l, int r) -> ll {
        return p[r] - (l ? p[l - 1] : 0LL); 
    };

    int q; cin >> q; 
    while (q--) {
        int ql, qr; 
        cin >> ql >> qr; 
        ql--; qr--; 

        ll s = get(ql, qr);  
        ll all = query(ql, qr); 
        ll nd = query2(ql, qr); // all must be >= nd 
        // cout << s << ' ' << all << ' ' << nd << '\n'; 

        if (all < nd) {
            cout << "-1\n"; 
        } else {
            cout << (s - all * (1LL + qr - ql)) << "\n";
        }
    }

}

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