#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;
vector<int> d;
vector<int> cumul_d;
vector<int> cumul_cumul_d;
int take_mod(int v){
if(v>=0){
return v%D;
}
else{
//cout<<v<<" "<<D+(v%D)<<endl;
return (D+(v%D))%D;
}
}
void precalc(){
vector<pair<int, int>> st;
a[0] = 0;
d.resize(n+1);
for(int i= 1; i<n; i++){
d[i] = take_mod(a[i+1]-a[i]);
}
cumul_d.resize(n+1);
for(int i = 1; i<=n; i++){
cumul_d[i] =cumul_d[i-1] + d[i-1];
//cout<<i<<" "<<cumul_d[i]<<endl;
}
cumul_cumul_d.resize(n+1);
for(int i = 1; i<=n; i++){
cumul_cumul_d[i] = cumul_cumul_d[i-1] + cumul_d[i];
}
left_low.resize(n+1);
for(int i = n; i>=0; i--){
int v= a[i]+cumul_d[n]-cumul_d[i];
while(st.size()>0 && st.back().second>=v){
left_low[st.back().first] = i;
st.pop_back();
}
st.push_back({i, v});
}
for(auto e: st){
left_low[e.first] = -1;
}
left_low[0] = -1;
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], max(0LL, cumul_cumul_d[i]-cumul_cumul_d[left_low[i]+1]) + (a[i]-cumul_d[i]+cumul_d[left_low[i]+1]) * (i-left_low[i])- (max(0LL, i-left_low[i]-1)) * cumul_d[left_low[i]+1]};
//cout<<i<<" "<<bl[0][i].first<<" "<<bl[0][i].second<<endl;
}
for(int step = 1; step<20; step++){
for(int i = 0; i<=n; i++){
if(bl[step-1][i].first ==-1){
bl[step][i] = bl[step-1][i];
}
else{
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){
//cout<<"detail "<<cumul_cumul_d[cur]-cumul_cumul_d[lim+1]<<" "<<(a[cur]-cumul_d[cur]+cumul_d[lim+1]) * (cur-lim)<<endl;
res += cumul_cumul_d[cur]-cumul_cumul_d[lim+1]+(a[cur]-cumul_d[cur]+cumul_d[lim+1]) * (cur-lim) - (cur-lim-1) * cumul_d[lim+1];
}
if(a[cur]-cumul_d[cur]+cumul_d[lim+1] < 0){
return -1;
}
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;
int bs = Bs(r, l-1);
if(bs == -1){
cout<<-1<<endl;
}
else{
cout<<(cumul[r]-cumul[l-1]-bs)/D<<endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
1628 KB |
Output is correct |
5 |
Correct |
5 ms |
1628 KB |
Output is correct |
6 |
Correct |
5 ms |
1116 KB |
Output is correct |
7 |
Correct |
5 ms |
1112 KB |
Output is correct |
8 |
Correct |
6 ms |
1372 KB |
Output is correct |
9 |
Correct |
5 ms |
1612 KB |
Output is correct |
10 |
Correct |
6 ms |
1628 KB |
Output is correct |
11 |
Correct |
5 ms |
1628 KB |
Output is correct |
12 |
Correct |
6 ms |
1368 KB |
Output is correct |
13 |
Correct |
6 ms |
1420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1108 ms |
110340 KB |
Output is correct |
2 |
Correct |
942 ms |
109680 KB |
Output is correct |
3 |
Correct |
403 ms |
2044 KB |
Output is correct |
4 |
Correct |
612 ms |
109768 KB |
Output is correct |
5 |
Correct |
618 ms |
109768 KB |
Output is correct |
6 |
Correct |
822 ms |
109140 KB |
Output is correct |
7 |
Correct |
823 ms |
109336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
407 ms |
5824 KB |
Output is correct |
2 |
Correct |
642 ms |
113600 KB |
Output is correct |
3 |
Correct |
655 ms |
113868 KB |
Output is correct |
4 |
Correct |
634 ms |
113620 KB |
Output is correct |
5 |
Correct |
614 ms |
113768 KB |
Output is correct |
6 |
Correct |
897 ms |
110756 KB |
Output is correct |
7 |
Correct |
902 ms |
110468 KB |
Output is correct |
8 |
Correct |
921 ms |
110364 KB |
Output is correct |
9 |
Correct |
920 ms |
110484 KB |
Output is correct |
10 |
Correct |
1037 ms |
109144 KB |
Output is correct |
11 |
Correct |
1051 ms |
109652 KB |
Output is correct |
12 |
Correct |
1066 ms |
112136 KB |
Output is correct |
13 |
Correct |
1036 ms |
112216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
642 ms |
91604 KB |
Output is correct |
2 |
Correct |
636 ms |
110184 KB |
Output is correct |
3 |
Correct |
520 ms |
25876 KB |
Output is correct |
4 |
Correct |
650 ms |
110420 KB |
Output is correct |
5 |
Correct |
623 ms |
100636 KB |
Output is correct |
6 |
Correct |
612 ms |
114836 KB |
Output is correct |
7 |
Correct |
628 ms |
90452 KB |
Output is correct |
8 |
Correct |
614 ms |
114876 KB |
Output is correct |
9 |
Correct |
652 ms |
109488 KB |
Output is correct |
10 |
Correct |
629 ms |
109168 KB |
Output is correct |
11 |
Correct |
650 ms |
110416 KB |
Output is correct |
12 |
Correct |
643 ms |
109392 KB |
Output is correct |
13 |
Correct |
613 ms |
113964 KB |
Output is correct |
14 |
Correct |
588 ms |
114876 KB |
Output is correct |
15 |
Correct |
623 ms |
113864 KB |
Output is correct |
16 |
Correct |
599 ms |
114628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
1628 KB |
Output is correct |
5 |
Correct |
5 ms |
1628 KB |
Output is correct |
6 |
Correct |
5 ms |
1116 KB |
Output is correct |
7 |
Correct |
5 ms |
1112 KB |
Output is correct |
8 |
Correct |
6 ms |
1372 KB |
Output is correct |
9 |
Correct |
5 ms |
1612 KB |
Output is correct |
10 |
Correct |
6 ms |
1628 KB |
Output is correct |
11 |
Correct |
5 ms |
1628 KB |
Output is correct |
12 |
Correct |
6 ms |
1368 KB |
Output is correct |
13 |
Correct |
6 ms |
1420 KB |
Output is correct |
14 |
Correct |
1108 ms |
110340 KB |
Output is correct |
15 |
Correct |
942 ms |
109680 KB |
Output is correct |
16 |
Correct |
403 ms |
2044 KB |
Output is correct |
17 |
Correct |
612 ms |
109768 KB |
Output is correct |
18 |
Correct |
618 ms |
109768 KB |
Output is correct |
19 |
Correct |
822 ms |
109140 KB |
Output is correct |
20 |
Correct |
823 ms |
109336 KB |
Output is correct |
21 |
Correct |
407 ms |
5824 KB |
Output is correct |
22 |
Correct |
642 ms |
113600 KB |
Output is correct |
23 |
Correct |
655 ms |
113868 KB |
Output is correct |
24 |
Correct |
634 ms |
113620 KB |
Output is correct |
25 |
Correct |
614 ms |
113768 KB |
Output is correct |
26 |
Correct |
897 ms |
110756 KB |
Output is correct |
27 |
Correct |
902 ms |
110468 KB |
Output is correct |
28 |
Correct |
921 ms |
110364 KB |
Output is correct |
29 |
Correct |
920 ms |
110484 KB |
Output is correct |
30 |
Correct |
1037 ms |
109144 KB |
Output is correct |
31 |
Correct |
1051 ms |
109652 KB |
Output is correct |
32 |
Correct |
1066 ms |
112136 KB |
Output is correct |
33 |
Correct |
1036 ms |
112216 KB |
Output is correct |
34 |
Correct |
642 ms |
91604 KB |
Output is correct |
35 |
Correct |
636 ms |
110184 KB |
Output is correct |
36 |
Correct |
520 ms |
25876 KB |
Output is correct |
37 |
Correct |
650 ms |
110420 KB |
Output is correct |
38 |
Correct |
623 ms |
100636 KB |
Output is correct |
39 |
Correct |
612 ms |
114836 KB |
Output is correct |
40 |
Correct |
628 ms |
90452 KB |
Output is correct |
41 |
Correct |
614 ms |
114876 KB |
Output is correct |
42 |
Correct |
652 ms |
109488 KB |
Output is correct |
43 |
Correct |
629 ms |
109168 KB |
Output is correct |
44 |
Correct |
650 ms |
110416 KB |
Output is correct |
45 |
Correct |
643 ms |
109392 KB |
Output is correct |
46 |
Correct |
613 ms |
113964 KB |
Output is correct |
47 |
Correct |
588 ms |
114876 KB |
Output is correct |
48 |
Correct |
623 ms |
113864 KB |
Output is correct |
49 |
Correct |
599 ms |
114628 KB |
Output is correct |
50 |
Correct |
621 ms |
121428 KB |
Output is correct |
51 |
Correct |
904 ms |
115024 KB |
Output is correct |
52 |
Correct |
905 ms |
118356 KB |
Output is correct |
53 |
Correct |
1036 ms |
116724 KB |
Output is correct |
54 |
Correct |
1031 ms |
119888 KB |
Output is correct |
55 |
Correct |
618 ms |
121172 KB |
Output is correct |
56 |
Correct |
602 ms |
117088 KB |
Output is correct |
57 |
Correct |
587 ms |
113776 KB |
Output is correct |
58 |
Correct |
590 ms |
113864 KB |
Output is correct |
59 |
Correct |
647 ms |
119572 KB |
Output is correct |
60 |
Correct |
603 ms |
117112 KB |
Output is correct |
61 |
Correct |
1049 ms |
116932 KB |
Output is correct |
62 |
Correct |
1041 ms |
116960 KB |
Output is correct |
63 |
Correct |
1036 ms |
119728 KB |
Output is correct |
64 |
Correct |
605 ms |
117312 KB |
Output is correct |