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
int n;int Q;
int ar[200005];
int rmq[22][200005];
int chmx(int l,int r){
int lg=__lg(r-l+1);
return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
signed main()
{
cin>>n>>Q;
for(int i=1;i<=n;i++){
cin>>ar[i];
rmq[0][i]=ar[i];
}
for(int i=1;i<=21;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
rmq[i][j]=max(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
}
while(Q--){
int t;int l;int r;
cin>>t>>l>>r;
l=max(1ll,r-t);
int ans=0;
for(int i=l;i<=r;i++){
ans+=chmx(max(1ll,i-t),i);
}
cout<<ans<<endl;
}
}
# | 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... |