oj.uz

Submission #1006368

# Submission time Handle Problem Language Result Execution time Memory
1006368 2024-06-23T21:31:21 Z juliany2 Fish 3 (JOI24_fish3) C++17
20 / 100
 300 ms 50004 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

struct LZ_ST {
    int sz;
    vector<ll> t, lz;

    void init(int n) {
        sz = n;
        t.resize(sz * 4 + 7);
        lz.resize(sz * 4 + 7);
    }

    inline void push(int v, int l, int r) {
        if (l != r && lz[v]) {
            int m = (l + r) / 2;
            t[v * 2] += lz[v] * (m - l + 1);
            t[v * 2 + 1] += lz[v] * (r - m);
            lz[v * 2] += lz[v];
            lz[v * 2 + 1] += lz[v];
        }
        lz[v] = 0;
    }

    void upd(int ql, int qr, ll x, int v, int l, int r) {
        if (r < ql || l > qr)
            return;
        if (l >= ql && r <= qr)
            t[v] += x * (r - l + 1), lz[v] += x;
        else {
            push(v, l, r);
            int m = (l + r) / 2;
            upd(ql, qr, x, v * 2, l, m);
            upd(ql, qr, x, v * 2 + 1, m + 1, r);

            t[v] = t[v * 2] + t[v * 2 + 1];
        }
    }
    void upd(int ql, int qr, ll x) {
        upd(ql, qr, x, 1, 1, sz);
    }

    ll query(int ql, int qr, int v, int l, int r) {
        if (r < ql || l > qr)
            return 0;
        if (l >= ql && r <= qr)
            return t[v];
        
        push(v, l, r);
        int m = (l + r) / 2;
        return query(ql, qr, v * 2, l, m) + query(ql, qr, v * 2 + 1, m + 1, r);
    }
    ll query(int ql, int qr) {
        return query(ql, qr, 1, 1, sz);
    }
};

const int N = 3e5 + 7;
int n, q;
vector<array<int, 2>> qry[N];
ll c[N], d;
ll ans[N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> d;

    for (int i = 1; i <= n; i++)
        cin >> c[i];

    cin >> q;

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        qry[r].push_back({l, i});
    }

    LZ_ST st;
    st.init(n + 1);

    stack<array<ll, 2>> s;
    s.push({(ll) 1e18, 1});

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            if (c[i] >= c[i - 1]) {
                ll dif = (c[i] - c[i - 1] + d - 1) / d;

                if (dif)
                    s.push({dif, i});
            }
            else {
                ll dif = (c[i - 1] - c[i] + d - 1) / d;

                while (dif) {
                    auto [x, j] = s.top();

                    ll take = min(x, dif);
                    x -= take, dif -= take;

                    st.upd(j, i - 1, take);

                    if (x == 0)
                        s.pop();
                }
            }
        }

        for (auto &[l, idx] : qry[i]) {
            ll x = c[l] - st.query(l, l) * d;
            ans[idx] = (x < 0 ? -1 : st.query(l, i));
        }
    }

    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Incorrect 2 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 43192 KB Output is correct
2 Correct 194 ms 42832 KB Output is correct
3 Incorrect 80 ms 19952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 23676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 39520 KB Output is correct
2 Correct 185 ms 43096 KB Output is correct
3 Correct 171 ms 26612 KB Output is correct
4 Correct 193 ms 46676 KB Output is correct
5 Correct 258 ms 46680 KB Output is correct
6 Correct 284 ms 49768 KB Output is correct
7 Correct 229 ms 44372 KB Output is correct
8 Correct 300 ms 50004 KB Output is correct
9 Correct 155 ms 42324 KB Output is correct
10 Correct 146 ms 42212 KB Output is correct
11 Correct 257 ms 46420 KB Output is correct
12 Correct 176 ms 45788 KB Output is correct
13 Correct 298 ms 49748 KB Output is correct
14 Correct 207 ms 45304 KB Output is correct
15 Correct 281 ms 49492 KB Output is correct
16 Correct 219 ms 45284 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Incorrect 2 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -