oj.uz

답안 #1006372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006372 2024-06-23T21:44:56 Z juliany2 Fish 3 (JOI24_fish3) C++17
27 / 100
 279 ms 42324 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;

                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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Incorrect 4 ms 10332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 226 ms 38688 KB Output is correct
2 Correct 193 ms 37968 KB Output is correct
3 Correct 67 ms 17216 KB Output is correct
4 Correct 182 ms 42324 KB Output is correct
5 Correct 176 ms 42068 KB Output is correct
6 Correct 154 ms 42080 KB Output is correct
7 Correct 143 ms 42068 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 21072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 35056 KB Output is correct
2 Correct 197 ms 38736 KB Output is correct
3 Correct 148 ms 22356 KB Output is correct
4 Correct 241 ms 38736 KB Output is correct
5 Correct 240 ms 39504 KB Output is correct
6 Correct 253 ms 42064 KB Output is correct
7 Correct 234 ms 37452 KB Output is correct
8 Correct 258 ms 41968 KB Output is correct
9 Correct 145 ms 37972 KB Output is correct
10 Correct 148 ms 37700 KB Output is correct
11 Correct 217 ms 38728 KB Output is correct
12 Correct 154 ms 37972 KB Output is correct
13 Correct 276 ms 41788 KB Output is correct
14 Correct 199 ms 37652 KB Output is correct
15 Correct 279 ms 42068 KB Output is correct
16 Correct 187 ms 37740 KB Output is correct

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Incorrect 4 ms 10332 KB Output isn't correct
5 Halted 0 ms 0 KB -