Submission #1084145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084145		Mike_Vu	Fish 3 (JOI24_fish3)	C++14	100 / 100	235 ms	38048 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

bool maximize(ll &x, ll y ){
    if (x < y) {x = y; return true;};
    return false;
}
bool minimize(ll &x, ll y){
    if (x > y) {x = y; return true;}
    return false;
}

struct BIT{
    int n;
    vector<ll> bit;
    BIT(int _n = 0) {
        n = _n;
        bit.assign(n+1, 0);
    }
    void update(int k, ll x) {
        while (k <= n) {
            bit[k] += x;
            k += k & (-k);
        }
    }
    ll getsum(int k) {
        ll res = 0;
        while (k > 0) {
            res += bit[k];
            k -= k & (-k);
        }
        return res;
    }
    ll query(int l, int r) {
        return getsum(r)-getsum(l-1);
    }
} bitcost, bitsum;
struct query{
    int l, r, id;
    ll ans;
    query(int u, int v, int i) {
        l = u;
        r = v;
        id = i;
    }
};
bool cmp1(query a, query b) {
    return a.r < b.r;
}
bool cmp2(query a, query b) {
    return a.id < b.id;
}

const int maxn = 3e5+5;
int n, q;
ll d, c[maxn], a[maxn];
vector<query> qu;

void input() {
    cin >> n >> d;
    c[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        //manghieu
        a[i] = c[i] - c[i-1];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qu.pb(query(l, r, i));
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //input
    input();
    //init
    bitsum = BIT(n);
    bitcost = BIT(n);
    sort(qu.begin(), qu.end(), cmp1);
    //vector<cou+pos>
    vector<pair<ll, int>> avai;
    int j = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= d) {
            avai.push_back({a[i]/d, i});
        }
        else if (a[i] < 0) {
            ll x = (-a[i]-1)/d+1;
            //need x
            //bit update
            bitsum.update(i, -x);
            bitcost.update(i, (-x)*(n-i+1));
            //fix x
            while (!avai.empty() && x > 0) {
                ll &cou = avai.back().first;
                int pos = avai.back().se;
                ll decval = min(cou, x);
                cou -= decval;
                x -= decval;
                //bit
                bitsum.update(pos, decval);
                bitcost.update(pos, decval*(n-pos+1));
                if (cou == 0) avai.pop_back();
            }
        }
//        for (int i = 1; i <= n; i++) {
//            cout << bitsum.query(i, i);
//        }
//        cout << "\n";
//        for (int i = 1; i <= n; i++) {
//            cout << bitcost.query(i, i);
//        }
//        cout << "\n\n";
        //solve queries offline
        while (j < q && qu[j].r == i) {
            int l = qu[j].l, r = qu[j].r;
            ll &ans = qu[j].ans;
            ++j;
            ll sum = bitsum.query(l+1, r);
            //start
            ans = 0;
            if (sum < 0) {
                ll can = max(0LL, c[l]/d);
                //need: -sum
                if (can+sum<0) {
                    ans = -1;
                    continue;
                }
                ans += (-sum)*(r-l+1);
            }
            ans += bitcost.query(l+1, r)-sum*(n-r);
        }
    }
    sort(qu.begin(), qu.end(), cmp2);
    for (int i = 0; i < q; i++) {
        cout << qu[i].ans << "\n";
    }
}
/*
4 2
3 1 2 1
1
1 3

4 2
0 1 0 1
3
1 2
2 3
1 1

5 1
3 1 4 1 5
3
1 5
2 4
3 5

6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6
*/

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