Submission #1033268

#TimeUsernameProblemLanguageResultExecution timeMemory
1033268Hectorungo_18Fish 3 (JOI24_fish3)C++14
0 / 100
422 ms5212 KiB
#include <bits/stdc++.h> using namespace std; string abc = "abcdefghijklmnopqrstuvwxyz"; #define int long long const int N = 2e5+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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...