Submission #1083462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083462		dwuy	Fish 3 (JOI24_fish3)	C++14	100 / 100	396 ms	54192 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;

struct BIT{
    int n;
    vector<int> tree;

    BIT(int n = 0){
        this->n = n;
        this->tree.assign(n + 5, 0);
    }

    void update(int idx, int val){
        for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
    }

    void update(int l, int r, int val){
        update(l, val);
        update(r + 1, -val);
    }

    int get(int idx){
        if(!idx) return -2e18;
        int res = 0;
        for(; idx; idx-=-idx&idx) res += tree[idx];
        return res;
    }
};

struct Node{
    int sum, lz;
    Node() : sum(0), lz(0) {}
};

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n = 0){
        this->n = n;
        this->tree.assign(n<<2|3, Node());
    }

    void down(int id, int l, int r){
        if(tree[id].lz == 0) return;
        int mid = (l + r)>>1;
        int val = tree[id].lz;
        tree[id<<1].lz += val;
        tree[id<<1].sum += val*(mid - l + 1);
        tree[id<<1|1].lz += val;
        tree[id<<1|1].sum += val*(r - mid);
        tree[id].lz = 0;
    }

    void update(int l, int r, int id, const int &u, const int &v, const int &val){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            tree[id].lz += val;
            tree[id].sum += val*(r - l + 1);
            return;
        }
        down(id, l, r);
        int mid = (l + r)>>1;
        update(l, mid, id<<1, u, v, val);
        update(mid + 1, r, id<<1|1, u, v, val);
        tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
    }

    void update(int l, int r, int val){
        update(1, n, 1, l, r, val);
    }

    int gsum(int l, int r, int id, const int &u, const int &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].sum;
        down(id, l, r);
        int mid = (l + r)>>1;
        return gsum(l, mid, id<<1, u, v) + gsum(mid + 1, r, id<<1|1, u, v);
    }

    int gsum(int l, int r){
        return gsum(1, n, 1, l, r);
    }
};

const int MX = 300005;
int n, q, D;
int a[MX];
int ans[MX];
vector<pii> Q[MX];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    SMT smt(n);
    BIT bit(n);
    bit.update(1, 1, a[1]);

    stack<int> st;
    st.push(1);

    for(int i=2; i<=n; i++){
        bit.update(i, i, a[i]);
        st.push(i);
        while(1){
            int dif = bit.get(st.top()) - bit.get(st.top() - 1);
            if(dif >= 0) break; else dif = -dif;
            int pos = st.top(); st.pop();
            int pre = st.top();
            int d = dif/D + !!(dif%D);
            bit.update(pre, pos - 1, -d*D);
            smt.update(pre, pos - 1, d);
        }
        for(pii qr: Q[i]){  
            int l, id;
            tie(l, id) = qr;
            if(bit.get(l) < 0) ans[id] = -1;
            else ans[id] = smt.gsum(l, i);
        }
    }
    for(int i=1; i<=q; i++) cout << ans[i] << '\n';

    return 0;
}

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