Submission #991057

#	Time	Username	Problem	Language	Result	Execution time	Memory
991057		grt	Fish 3 (JOI24_fish3)	C++17	100 / 100	341 ms	66336 KiB

Main

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10;

struct SegTree {
    ll T[(1 << 20)];
    int R;
    void upd(int a, ll x) {
        a += R;
        T[a] += x;
        while (a > 1) {
            a >>= 1;
            T[a] += x;
        }
    }
    ll qr(int a, int b) {
        a += R; b += R;
        if (a > b) return 0LL;
        ll w = T[a] + (a != b ? T[b] : 0LL);
        while (a/2 != b/2) {
            if (a % 2 == 0) w += T[a + 1];
            if (b % 2 == 1) w += T[b - 1];
            a >>= 1;
            b >>= 1;
         }
        return w;
    }
    void init(int n) {
        R = 1;
        while (R < n) R <<= 1;
        for (int i = 0; i < 2 * R; ++i) T[i] = 0;
    }
    int go_down() {
        int v = 1;
        while (v < R) {
            if (T[2 * v + 1] != 0) v = v*2 + 1;
            else v = v*2;
        }
        return v - R;
    }
};

vector<pair<int,int>>qrs[nax];
ll ans[nax];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    ll d;
    cin >> n >> d;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    cin >> q;
    vector<ll> demands(n);

    for (int i = 1; i < n; ++i) {
        demands[i] = a[i] - a[i - 1];
        if (demands[i] < 0) {
            demands[i] = (abs(demands[i]) - 1) / d + 1;
        } else {
            demands[i] = -(demands[i] / d);
        }
    }

    for (int l,r, i = 0; i < q; ++i) {
        cin >> l >> r;
        l--, r--;
        qrs[r].emplace_back(l, i);
    }
    
    SegTree s, lft, closed, total;
    s.init(n);
    lft.init(n);
    closed.init(n);
    total.init(n);
    for (int i = 1; i < n; ++i) {
        // update value i
        //cerr << "i: " << i << " " << demands[i] << "\n";
        if (demands[i] < 0) {
            s.upd(i, -demands[i]); // I can give that many
        } else {
            lft.upd(i, demands[i] * i);
            total.upd(i, demands[i]);
            while (demands[i] > 0) {
                if (s.T[1] == 0) break;
                int v = s.go_down();
                ll me = min(demands[i], s.qr(v,v));
                s.upd(v, -me);
                demands[i] -= me;
                closed.upd(v, me);
                lft.upd(v, -me * v);
                //cerr << "segment: " << v << "->" << i << " " << me << " times\n";
            }
        }
        for (auto [l, id] : qrs[i]) {
            ll open = total.qr(l + 1, i) - closed.qr(l + 1, i);
            ll res = lft.qr(l + 1, i);
            ll me = a[l] / d;
            //cerr << "(" << total.qr(l+1,i) << " " << closed.qr(l+1, i) << ")"  << " " << res << " " << me << "\n";
            if (me < open) {
                ans[id] = -1;
            } else {
                ans[id] = res - (ll)l * open;
            }
        }
    }

    for (int i = 0; i < q; ++i) cout << ans[i] << "\n";
}

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