Submission #1097052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097052		vladilius	Fish 3 (JOI24_fish3)	C++17	100 / 100	473 ms	66388 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();

struct DS{
    vector<pair<ll, ll>> t;
    vector<ll> p;
    int n;
    DS(int ns){
        n = ns;
        t.resize(4 * n, {0, 0});
        p.assign(4 * n, inf);
    }
    void push(int& v, int& tl, int& tr){
        if (p[v] == inf) return;
        int tm = (tl + tr) / 2, vv = 2 * v;
        t[vv].ff = p[v] * (tm - tl + 1);
        t[vv + 1].ff = p[v] * (tr - tm);
        t[vv].ss = t[vv + 1].ss = p[vv] = p[vv + 1] = p[v];
        p[v] = inf;
    }
    int find(int v, int tl, int tr, ll& x){
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v, tl, tr);
        if (t[vv].ss < x){
            return find(vv, tl, tm, x);
        }
        return find(vv + 1, tm + 1, tr, x);
    }
    void ch(int v, int tl, int tr, int& l, int& r, ll& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            t[v].ff = x * (tr - tl + 1);
            t[v].ss = p[v] = x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v, tl, tr);
        ch(vv, tl, tm, l, r, x);
        ch(vv + 1, tm + 1, tr, l, r, x);
        t[v].ff = t[vv].ff + t[vv + 1].ff;
        t[v].ss = min(t[vv].ss, t[vv + 1].ss);
    }
    void upd(int p, ll x){
        int t = min(find(1, 1, n, x), p);
        ch(1, 1, n, t, p, x);
    }
    ll get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return t[v].ff;
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v, tl, tr);
        return get(vv, tl, tm, l, r) + get(vv + 1, tm + 1, tr, l, r);
    }
    ll get(int l, int r){
        if (l > r) return 0;
        return get(1, 1, n, l, r);
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n; ll d; cin>>n>>d;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    vector<ll> x(n);
    for (int i = 1; i < n; i++){
        x[i] = -floor(1.0 * (a[i + 1] - a[i]) / d);
    }
    vector<ll> y(n);
    for (int i = 1; i < n; i++){
        y[i] = y[i - 1] + x[i];
    }
    
    vector<ll> p(n);
    for (int i = 1; i < n; i++){
        p[i] = p[i - 1] + y[i];
    }
    
    int q; cin>>q;
    vector<pii> end[n + 1];
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        end[r].pb({l, i});
    }
 
    vector<ll> out(q + 1);
    DS T(n);
    for (int r = 1; r <= n; r++){
        T.upd(r, y[r - 1]);
        for (auto [l, ii]: end[r]){
            ll h = y[l - 1] - T.get(l, l);
            if ((a[l] + h * d) < 0){
                out[ii] = -1;
                continue;
            }
            ll sum = p[r - 1] - ((l > 1) ? p[l - 2] : 0);
            out[ii] = max(0LL, T.get(l, r) - sum);
        }
    }
    for (int i = 1; i <= q; i++){
        cout<<out[i]<<"\n";
    }
}

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