Submission #1041074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041074		_callmelucian	Fish 3 (JOI24_fish3)	C++14	100 / 100	1186 ms	90696 KiB

Main

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct IT {
    vector<ll> tr, lazy, lo;
    vector<int> vec;

    IT (int sz) : tr(4 * sz), lazy(4 * sz), lo(4 * sz) {}

    ll getSum (int k, int l, int r) {
        return tr[k] + ll(r - l + 1) * lazy[k];
    }

    ll getLo (int k) {
        return lo[k] + lazy[k];
    }

    void refine (int k, int l, int r, int mid) {
        lo[k] = min(getLo(2 * k), getLo(2 * k + 1));
        tr[k] = getSum(2 * k, l, mid) + getSum(2 * k + 1, mid + 1, r);
    }

    void pushDown (int k, int l, int r, int mid) {
        lazy[2 * k] += lazy[k], lazy[2 * k + 1] += lazy[k], lazy[k] = 0;
        refine(k, l, r, mid);
    }

    void update (int a, int b, ll val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            lazy[k] += val;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(k, l, r, mid);
        update(a, b, val, 2 * k, l, mid);
        update(a, b, val, 2 * k + 1, mid + 1, r);
        refine(k, l, r, mid);
    }

    ll querySum (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return getSum(k, l, r);
        int mid = (l + r) >> 1;
        pushDown(k, l, r, mid);
        return querySum(a, b, 2 * k, l, mid) + querySum(a, b, 2 * k + 1, mid + 1, r);
    }

    ll queryLo (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return LLONG_MAX;
        if (a <= l && r <= b) return getLo(k);
        int mid = (l + r) >> 1;
        pushDown(k, l, r, mid);
        return min(queryLo(a, b, 2 * k, l, mid), queryLo(a, b, 2 * k + 1, mid + 1, r));
    }

    void walk (int a, int b, int k, int l, int r) {
        if (b < l || r < a || getLo(k) > 0) return;
        if (l == r) {
            vec.push_back(l);
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(k, l, r, mid);
        walk(a, b, 2 * k, l, mid);
        walk(a, b, 2 * k + 1, mid + 1, r);
    }

    vector<int> findZero (int a, int b, int k, int l, int r) {
        vec.clear();
        walk(a, b, k, l, r);
        return vec;
    }
};

const int mn = 3e5 + 5;
ll a[mn], base[mn], bound[mn], ans[mn];
vector<pii> qry[mn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; ll D; cin >> n >> D;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        base[i] = a[i] % D, bound[i] = a[i] / D;
    }

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

    IT tree(n), cur(n);
    ll last = LLONG_MAX;
    priority_queue<int> pq; pq.push(0);

    for (int i = n; i >= 1; i--) {
        last = min(bound[i], last - (base[i] > base[i + 1]));
        tree.update(i, i, bound[i] - last, 1, 1, n);
        cur.update(i, i, last, 1, 1, n);
        if (bound[i] == last) pq.push(i);
    }

    for (int i = n; i >= 1; i--) {
        if (pq.top() == i) pq.pop();
        ll decr = tree.queryLo(i, i, 1, 1, n);

        while (decr) {
            ll tmp = tree.queryLo(pq.top() + 1, i, 1, 1, n);
            tree.update(pq.top() + 1, i, -tmp, 1, 1, n);
            cur.update(pq.top() + 1, i, tmp, 1, 1, n);
            if (pq.top() + 1 <= i - 1) {
                vector<int> pos = tree.findZero(pq.top() + 1, i - 1, 1, 1, n);
                for (int u : pos) pq.push(u);
            }
            decr -= tmp;
        }

        for (auto [l, id] : qry[i]) {
            if (cur.queryLo(l, i, 1, 1, n) < 0) ans[id] = -1;
            else ans[id] = tree.querySum(l, i, 1, 1, n);
        }
    }

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

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:132:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |         for (auto [l, id] : qry[i]) {
      |                   ^

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