Submission #1165779

#TimeUsernameProblemLanguageResultExecution timeMemory
1165779abcdxyz123Fish 3 (JOI24_fish3)C++17
9 / 100
2098 ms60900 KiB
#include<bits/stdc++.h> #define ll long long #define maxn 300005 using namespace std; int n; ll d; ll a[maxn]; ll b[maxn]; ll sb[maxn]; ll dif[maxn]; ll sdif[maxn]; int lg[maxn]; ll rmq[maxn][20]; ll get_minB(int l,int r) { int k=__lg(r-l+1); return min(rmq[l][k],rmq[r-(1<<k)+1][k]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>d; lg[1]=0; for(int i=2;i<=n;i++) { lg[i]=lg[i/2]+1; } for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { dif[i]=((a[i+1]-a[i])%d+d)%d; sdif[i]=sdif[i-1]+dif[i]; b[i]=rmq[i][0]=(a[i]-sdif[i-1]); sb[i]=sb[i-1]+b[i]; } for(int k=1;k<=lg[n]+1;k++) { for(int i=1;i+(1<<k)-1<=n;i++) { rmq[i][k]=min(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]); } } int q; cin>>q; while(q--) { int l,r; cin>>l>>r; if(get_minB(l,r)<-(sdif[l-1]-a[l]%d)) { cout<<-1<<'\n'; continue; } //cout<<'\n'; int pre=r; ll ds=0; for(int i=r-1;i>=l;i--) { if(b[i]>=b[pre]) { } else { ds+=-(pre-i)*b[pre]; pre=i; } } ds+=(sb[r]-sb[l-1])-(pre-l+1)*b[pre]; cout<<ds/d<<'\n'; } } /* s[i]=s[i-3]+(a[i-2]-s[i-3])%mod+(a[i-1]-a[i-2])%mod+(a[i]-a[i-1])%mod s[i]=(a[l])%mod+(a[l+1]-a[l])%mod+...+(a[i]-a[i-1])%mod (a[i]-sdif[i-1])+(sdif[l-1]-a[l]%d) Voi mot thang r co dinh thi tat cac so chi cong len mot luong co dinh (a[i]-sdif[i-1])+(sdif[l-1]-a[l]%d)>=0 */
#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...