Submission #984809

#	Time	Username	Problem	Language	Result	Execution time	Memory
984809		vjudge2	Fish 3 (JOI24_fish3)	C++17	100 / 100	606 ms	65260 KiB

Main

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

#define int long long
const int INF = 1e18;

struct node {
    int sum, sz, mx;
};

struct segtree {
    int size = 1;
    vector<node> seg;
    vector<int> lazy;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 1, (node) {0, 0, 0});
        lazy.assign(2 * size + 1, -1);
    }
    void pull(int id) {
        seg[id].sum = seg[id * 2].sum + seg[id * 2 + 1].sum;
        seg[id].sz = seg[id * 2].sz + seg[id * 2 + 1].sz;
        seg[id].mx = max(seg[id * 2].mx, seg[id * 2 + 1].mx);
    }
    void build(int l, int r, int id) {
        if (l == r) {
            seg[id].sz = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, id * 2);
        build(mid + 1, r, id * 2 + 1);
        pull(id);
    }
    void push(int id) {
        if (lazy[id] != -1) {
            seg[id].sum = lazy[id] * seg[id].sz;
            seg[id].mx = lazy[id];
        }
        if (id < size) for (int i = 0; i < 2; i++) if (lazy[id] != -1) lazy[id * 2 + i] = lazy[id];
        lazy[id] = -1;
    }
    void update(int ql, int qr, int val, int l, int r, int id) {
        push(id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            lazy[id] = val;
            push(id);
            return;
        }
        int mid = (l + r) / 2;
        update(ql, qr, val, l, mid, id * 2) ;
        update(ql, qr, val, mid + 1, r, id * 2 + 1);
        pull(id);
    }
    int query(int ql, int qr, int l, int r, int id) {
        push(id);
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return seg[id].sum;
        int mid = (l + r) / 2;
        return query(ql, qr, l, mid, id * 2) + query(ql, qr, mid + 1, r, id * 2 + 1);
    }
    int find(int ql, int qr, int x, int l, int r, int id) {
        push(id);
        // cout << l << ' ' << r << ' ' << x << ' ' << seg[id].mx << '\n';
        if (qr < l || r < ql) return -1;
        if (l == r && seg[id].mx > x) return l;
        else if (l == r) return -1;
        int mid = (l + r) / 2;
        int ans = -1;
        if (seg[id * 2].mx > x) ans = find(ql, qr, x, l, mid, id * 2);
        if (ans == -1) return find(ql, qr, x, mid + 1, r, id * 2 + 1);
        return ans;
    }
} st;

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k, q;
    cin >> n >> k;
    vector<int> c(n+1), ac(n+1, 0), a(n+1, 0), d(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        ac[i] = c[i];
    }
    for (int i = n - 1; i >= 1; i--) {
        if (ac[i] > ac[i + 1]) {
            int diff = ac[i] - ac[i + 1];
            diff = (diff + k - 1) / k;
            a[i] += diff;
            ac[i] -= diff * k;
            d[i] = diff;
        }
    }
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    st.init(n + 1);
    st.build(1, n, 1);
    vector<vector<pair<int, int>>> qry(n+1);
    cin >> q;
    vector<int> ans(q+1, 0);
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        qry[r].push_back({l, i});
    }
    // for (int i = 1; i <= n; i++) cout << d[i] << ' ';
    // cout << '\n';
    for (int r = 1; r <= n; r++) {
        if (r > 1) {
            int id = st.find(1, r - 1, d[r], 1, n, 1);
            // cout << "id: " << id << '\n';
            if (id == -1) id = r;
            if (id <= r) {
                // cout << "update: " << id << ' ' << r << ' ' << d[r] << '\n';
                st.update(id, r, d[r], 1, n, 1);
            }
        } else {
            // cout << "update: " << 1 << " " << 1 << " " << d[1] << "\n";
            st.update(1, 1, d[1], 1, n, 1);
        }
        for (auto& [l, idx] : qry[r]) {
            int v = st.query(l, l, 1, n, 1);
            if (ac[l] + k * v < 0) ans[idx] = -1;
            else ans[idx] = a[r] - a[l - 1] - st.query(l, r, 1, n, 1);
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

// -5 -7 -6 -3 -4 -5 0

// -3 -3 -4 -5
// then take sum of negative "caused" by back element

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