Submission #1033273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033273		Hectorungo_18	Fish 3 (JOI24_fish3)	C++17	0 / 100	502 ms	19540 KiB

Main

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

string abc = "abcdefghijklmnopqrstuvwxyz";

#define int long long 
const int N = 3e5+7;
int a[N], t[4*N];

void merge(int v){
    if(min(t[2*v], t[2*v+1]) == -2e18-7){
        t[v]=-2e18-7;
        return;
    }
    
    t[v]=t[2*v]+t[2*v+1];
}

void in(int v, int tl, int tr){
    if(tl == tr){
        t[v]=a[tl];
        return;
    }
    int tm=(tl+tr)/2;
    in(2*v, tl, tm);
    in(2*v+1, tm+1, tr);
    merge(v);
}

int get(int v, int tl, int tr, int l, int r){
    if(tl == l && tr == r){
        return t[v];
    }
    int tm = (tl+tr)/2;
    if(tm >= r) return get(2*v, tl, tm, l, r);
    if(tm < l) return get(2*v+1, tm+1, tr, l, r);
    return get(2*v, tl, tm, l, tm)+get(2*v+1, tm+1, tr, tm+1, r);
}


void solve(){

    int n, k;
    cin >> n >> k;
    vector<int> v(n+1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    a[n]=0;
    for(int i = 1; i < n; i++){
        if(v[i] <= v[i+1]){
            a[i]=0;
        }
        else{
            int dif = v[i]-v[i+1];
            int aux = k-dif%k;
            if(aux == k) aux = 0;
            int ans = aux;
            // if(k-aux == k) ans = 0;
            if(ans > v[i+1]){
                a[i]=-2e18-7;
                continue;
            }
            ans+=(v[i]-(v[i+1]-aux))/k;
            a[i]=ans;
        }
        // cout << a[i] << " ";
        
    }
    // cout << "t" << endl;
    in(1, 1, n);

    int q;
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        if(r <= l){
            cout << 0 << endl;
        }
        else{
            int ans = get(1, 1, n, l, r-1);
            if(ans >= 0) cout << ans << endl;
            else cout << -1 << endl;
        }
    }

}


signed main(){
    int t = 1;

    while(t--){
        solve();
    }
}

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