This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353, mod2=998244353ll*998244353;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, d; cin >> n >> d;
vector<int> a(n);
for(auto &i: a) cin >> i;
vector<int> dp(n+1, 0), v(n, 0), p(n, 0), pref(n, 0);
int val=0;
for(int i=n-2; i>=0; i--){
if(a[i]%d > a[i+1]%d){
val--;
}
v[i]=val;
dp[i]=dp[i+1]+val;
}
auto query=[&](int l, int r){
int val1=a[r]/d, val2=a[r]%d;
int ans=0;
int sum=0;
for(int i=r-1; i>=l; i--){
if(a[i]%d>val2){
val1--;
}
val2=a[i]%d;
val1=min(val1, a[i]/d);
sum+=a[i]/d-val1;
}
if(val1<0) return -1LL;
else return sum;
};
p[0]=a[0]-a[0]%d;
for(int i=1; i<n; i++){
p[i]+=p[i-1]+a[i]-a[i]%d;
}
pref=a;
for(int i=1; i<n; i++) pref[i]+=pref[i-1];
int q; cin >> q;
int f=1;
for(int i=1; i<n; i++){
if(a[i-1]<a[i]) f=0;
}
/* if(f){
while(q--){
int l, r; cin >> l >> r;
l--; r--;
int val=-(v[l]-v[r]);
if(l==r) cout<<0<<"\n";
else if(val*d >a[r]) cout<<-1<<"\n";
else{
int mi=(dp[l]-dp[r+1]);
int sum=p[r]-(l==0?0:p[l-1]);
sum+=mi*d;
cout<<sum/d<<"\n";
}
}
}*/
if(n<=3000&&q<=3000){
while(q--){
int l, r; cin >> l >> r;
l--; r--;
cout<<query(l, r)<<"\n";
}
}
else{
int f=1;
for(int i=0; i<n; i++){
if(a[i]>=2) f=0;
}
if(f){
while(q--){
int l, r; cin >> l >> r;
l--; r--;
int val=pref[r]-(l==0?0:pref[l-1]);
if(val==r-l+1||(pref[r]-pref[r-val])==val){
cout<<0<<"\n";
}
else{
if(d==1){
int j=val-(pref[r]-pref[r-val]);
cout<<j<<"\n";
}
else{
cout<<-1<<"\n";
}
}
}
}
}
}
Compilation message (stderr)
Main.cpp: In lambda function:
Main.cpp:31:13: warning: unused variable 'ans' [-Wunused-variable]
31 | int ans=0;
| ^~~
Main.cpp: In function 'int main()':
Main.cpp:55:9: warning: variable 'f' set but not used [-Wunused-but-set-variable]
55 | int f=1;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |