#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, d;
vector<int> a;
vector<int> left_low;
vector<vector<pair<int, int>>> bl;
vector<int> cumul;
void precalc(){
vector<int> st;
a[0] = 0;
left_low.resize(n+1);
for(int i = n; i>=0; i--){
while(st.size()>0 && a[st.back()]>=a[i]){
left_low[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
left_low[0] = 0;
bl.resize(20);
for(int i = 0; i<20; i++){
bl[i].resize(n+1);
}
for(int i = 0; i<=n; i++){
bl[0][i] = {left_low[i], a[i] * (i-left_low[i])};
}
for(int step = 1; step<20; step++){
for(int i = 0; i<=n; i++){
auto lh = bl[step-1][bl[step-1][i].first];
bl[step][i]={lh.first, lh.second + bl[step-1][i].second};
}
}
}
int Bs(int cur, int lim){
int res = 0;
for(int step = 19; step>=0; step--){
if(bl[step][cur].first>=lim){
res += bl[step][cur].second;
cur = bl[step][cur].first;
}
}
if(cur>lim){
res += (cur-lim) * a[cur];
}
return res;
}
signed main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>n>>d;
a.resize(n+1);
cumul.resize(n+1);
cumul[0] = 0;
for(int i = 1; i<=n; i++){
cin>>a[i];
cumul[i] = cumul[i-1] + a[i];
}
precalc();
int q;
cin>>q;
for(int i =0; i<q; i++){
int l, r;
cin>>l>>r;
cout<<cumul[r]-cumul[l-1]-Bs(r, l-1)<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
456 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
986 ms |
107748 KB |
Output is correct |
2 |
Correct |
856 ms |
107208 KB |
Output is correct |
3 |
Incorrect |
406 ms |
5064 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
403 ms |
8588 KB |
Output is correct |
2 |
Correct |
621 ms |
114244 KB |
Output is correct |
3 |
Correct |
624 ms |
114440 KB |
Output is correct |
4 |
Correct |
593 ms |
114344 KB |
Output is correct |
5 |
Correct |
585 ms |
114256 KB |
Output is correct |
6 |
Correct |
888 ms |
107952 KB |
Output is correct |
7 |
Correct |
869 ms |
108108 KB |
Output is correct |
8 |
Correct |
906 ms |
111080 KB |
Output is correct |
9 |
Correct |
933 ms |
111152 KB |
Output is correct |
10 |
Correct |
1045 ms |
109684 KB |
Output is correct |
11 |
Correct |
991 ms |
109704 KB |
Output is correct |
12 |
Correct |
1000 ms |
112932 KB |
Output is correct |
13 |
Correct |
1014 ms |
112880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
636 ms |
90284 KB |
Output is correct |
2 |
Correct |
607 ms |
107600 KB |
Output is correct |
3 |
Correct |
499 ms |
28488 KB |
Output is correct |
4 |
Correct |
690 ms |
110928 KB |
Output is correct |
5 |
Correct |
627 ms |
101512 KB |
Output is correct |
6 |
Correct |
595 ms |
114380 KB |
Output is correct |
7 |
Correct |
610 ms |
91928 KB |
Output is correct |
8 |
Correct |
586 ms |
114924 KB |
Output is correct |
9 |
Incorrect |
640 ms |
107612 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
456 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |