Submission #1062870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062870		matu	Fish 3 (JOI24_fish3)	C++17	0 / 100	2057 ms	11060 KiB

Main

#include <bits/stdc++.h>


using namespace std;

const long double eps = 1e-9;

typedef long long ll;
typedef long double ld;
const int mod = 998244353;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator*(Mint oth)
    {
        return 1LL * val * oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint fp(Mint a, long long n){
        Mint p = 1;
        while(n){
            if(n & 1){
                p = p * a;
            }
            a = a * a;
            n /= 2;
        }
        return p;
    }
    Mint operator/(Mint oth){
        Mint invers = fp(oth, mod - 2);
        return 1LL * val * invers.val;
    }
    friend ostream& operator << (ostream& os, const Mint& lol){
        os << lol.val;
        return os;
    }
};
struct AINT{
    vector<ll> aint, lazy;
    AINT(int n){
        aint.assign(n * 4 + 1, 0);
        lazy.assign(n * 4 + 1, 0);
    }
    void update(int v, int tl, int tr, int l, int r, int val){
        if(lazy[v]){
            aint[v] += lazy[v];
            if(tl != tr){
                lazy[v * 2] += lazy[v];
                lazy[v * 2 + 1] += lazy[v];
            }
            lazy[v] = 0;
        }
        if(l <= tl && r >= tr){
            aint[v] += val;
            if(tl != tr){
                lazy[v * 2] += val;
                lazy[v * 2 + 1] += val;
            }
            return;
        }
        if(l > tr || r < tl) return;
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm,l,r,val);
        update(v * 2 + 1, tm + 1, tr, l, r,val);
        aint[v] = aint[v * 2] + aint[v * 2 + 1];
    }
    ll query(int v, int tl, int tr, int l, int r){
        if(lazy[v]){
            aint[v] += lazy[v];
            if(tl != tr){
                lazy[v * 2] += lazy[v];
                lazy[v * 2 + 1] += lazy[v];
            }
            lazy[v] = 0;
        }
        if(l <= tl && r >= tr) return aint[v];
        if(l > tr || r < tl) return 0;
        int tm = (tl + tr) / 2;
        return query(v * 2, tl, tm,l, r) +  query(v * 2 + 1, tm + 1, tr, l, r);
    }
};

int red =0;
int ______________________________________________________________________________________________________________________________________________;



void solve(){
    ll n, d;
    cin >> n >> d;
    vector<ll> v(n + 1), ct(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    // vector<vector<pair<int,int>>> lr(n + 1);
    // int q;
    // cin >> q;
    // for(int i = 1; i <= q; i++){
    //     int l,r;
    //     cin >> l >> r;
    //     lr[r].push_back({l,i});
    // }
    // AINT aint(n + 1);
    // for(int i = 1; i <= n; i++){
    //     aint.update(1,1,n, i,i, v[i]);
    // }
    // stack<ll> s;
    // for(int i = 1; i <= n; i++){
    //     while(s.size() && v[s.top()] > v[i]){
    //         aint.update(1,1,n, s.top(), n, ct[s.top()]);
    //         s.pop();
    //     }
    //     if(s.size()){
    //         ct[i] = v[i] - v[s.top()];
    //         aint.update(1,1,n, i, n, -ct[i]);
    //     }else{
    //         ct[i] = v[i];
    //         aint.update(1,1,n, 1, n, -ct[i]);
    //     }
    //     s.push(i);

    //     for(auto j : lr[i]){

    //     }
    // }
    int q;
    cin >> q;

    while(q--){
        int l,r;
        cin >> l >> r;
        stack<int> s;
        vector<ll> mars(n + 2), minim(n + 2, 1e18);
        ll tl = 0;
        for(int i = r; i >= l; i--){
            minim[i] = min(minim[i + 1], v[i]);
        }
        ll ans = 0;
        ll m1 = 1e18;
        ll sm = 0;
        for(int i = l; i <= r; i++){
            ll pl = (v[i] - tl + d) %d;
            if(tl + pl > minim[i]){
                ans = -1;
                break;
            }else{
                tl += pl;
                m1 = min(m1, (v[i] - tl));
                sm += (v[i] - tl);
            }
        }

        if(!ans){
            cout << (ll)(sm - (ll)(r-l+1)*m1)/d - (d == 1 ? v[r] - m1 : 0) << '\n';
        }else{
            cout << ans << '\n';
        }
    }
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    if(red) cin >> t;
    while(t--){
        solve();
    }
}

/*


10
10 4
10 2
9 10
4 3
5 1
5 8
7 1
6 8
1 10

15, 12, 9, 3, 0
*/

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