Submission #1165761

#TimeUsernameProblemLanguageResultExecution timeMemory
1165761abcdxyz123Fish 3 (JOI24_fish3)C++17
9 / 100
2095 ms10104 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 dif[maxn]; ll sdif[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>d; 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]; } int q; cin>>q; while(q--) { int l,r; cin>>l>>r; int flag=0; for(int i=l;i<=r;i++) { b[i]=(a[i]-sdif[i-1]); //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 if((a[i]-sdif[i-1])+(sdif[l-1]-a[l]%d)<0) { flag=1; break; } //cout<<b[i]<<' '; } //cout<<'\n'; if(flag) { cout<<-1<<'\n'; continue; } //cout<<'\n'; int pre=r; ll sum=b[r]+(sdif[l-1]-a[l]%d); ll ds=0; for(int i=r-1;i>=l;i--) { if(b[i]>=b[pre]) { sum+=b[i]+(sdif[l-1]-a[l]%d); } else { //cout<<pre<<' '<<i<<'\n'; ds+=(sum- (pre-i)*b[pre] ); pre=i; sum=b[i]+(sdif[l-1]-a[l]%d); } } //cout<<sum<<' '<<pre<<'\n'; ds+=sum-(pre-l+1)*b[pre]; cout<<(ds-(r-l+1)*(sdif[l-1]-a[l]%d))/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) */
#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...