Submission #979022

#	Time	Username	Problem	Language	Result	Execution time	Memory
979022		abc864197532	Fish 3 (JOI24_fish3)	C++17	100 / 100	494 ms	82964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int mod = 998244353, N = 300005;

struct Seg {
    int l, r, m;
    ll lz, sum;
    Seg* ch[2];
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lz(0), sum(0) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m);
            ch[1] = new Seg(m, r);
        }
    }
    void pull() {
        sum = ch[0]->sum + ch[1]->sum;
    }
    void give(ll x) {
        lz += x, sum += x * (r - l);
    }
    void push() {
        if (!lz) {
            return;
        }
        ch[0]->give(lz), ch[1]->give(lz), lz = 0;
    }
    void add(int a, int b, ll v) {
        if (a <= l && r <= b) {
            give(v);
        } else {
            push();
            if (a < m) {
                ch[0]->add(a, b, v);
            }
            if (m < b) {
                ch[1]->add(a, b, v);
            }
            pull();
        }
    }
    ll query(int a, int b) {
        if (a <= l && r <= b) {
            return sum;
        }
        push();
        ll ans = 0;
        if (a < m) {
            ans += ch[0]->query(a, b);
        }
        if (m < b) {
            ans += ch[1]->query(a, b);
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    ll d;
    cin >> n >> d;
    vector <ll> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = a[i] % d, a[i] /= d;
    }
    // b[i] > b[i + 1] -> a[i] + add[i] <= a[i + 1] + add[i + 1]
    vector <int> add(n);
    for (int i = 1; i < n; ++i) if (b[i - 1] > b[i]) {
        add[i - 1]++;
    }
    for (int i = n - 2; i >= 0; --i) {
        add[i] += add[i + 1];
    }
    vector <ll> pre_a(n + 1);
    for (int i = 0; i < n; ++i) {
        a[i] += add[i];
        pre_a[i + 1] = pre_a[i] + a[i];
    }
    int q;
    cin >> q;
    vector <vector <pii>> queries(n + 1);
    for (int i = 0, l, r; i < q; ++i) {
        cin >> l >> r, --l, --r;
        queries[r].emplace_back(l, i);
    }
    Seg root(0, n);
    vector <array <ll, 3>> stk;
    vector <ll> ans(q);
    for (int i = 0; i < n; ++i) {
        // push i
        int lstl = i;
        while (!stk.empty() && stk.back()[2] >= a[i]) {
            root.add(stk.back()[0], stk.back()[1], -stk.back()[2]);
            lstl = stk.back()[0];
            stk.pop_back();
        }
        root.add(lstl, i + 1, a[i]);
        stk.pb({lstl, i + 1, a[i]});
        // handle query
        for (auto [l, id] : queries[i]) {
            ll suma = root.query(l, i + 1);
            ll lst = root.query(l, l + 1);
            if (lst - add[l] < 0) {
                ans[id] = -1; 
            } else {
                ans[id] = (pre_a[i + 1] - pre_a[l]) - suma;
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In constructor 'Seg::Seg(int, int)':
Main.cpp:13:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lz(0), sum(0) {
      |                                            ~~^~~

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