#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,k,q;
int arr[300005];
int brr[300005];
int pref1[300005];
int pref2[300005];
ii nxt[300005][20];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>k;
rep(x,1,n+1) cin>>arr[x];
rep(x,1,n+1) brr[x]=arr[x-1]-arr[x];
int L=1e18/k;
rep(x,1,n+1) brr[x]+=(-brr[x]+k*L)%k;
rep(x,1,n+1) pref1[x]=pref1[x-1]+brr[x];
rep(x,1,n+1) pref2[x]=pref2[x-1]+brr[x]*x;
int P=0;
vector<ii> v={{4e18,0}};
rep(x,1,n+1){
P+=brr[x];
while (!v.empty() && v.back().fi<P) v.pob();
int y=v.back().se;
nxt[x][0]={y,(pref2[x]-pref2[y+1])-(pref1[x]-pref1[y+1])*(y+1)};
v.pub({P,x});
}
rep(y,1,20) rep(x,1,n+1){
int u=nxt[x][y-1].fi;
nxt[x][y]={
nxt[u][y-1].fi,
nxt[x][y-1].se+nxt[u][y-1].se
};
}
cin>>q;
while (q--){
int l,r; cin>>l>>r;
int ans=0;
rep(x,20,0) if (nxt[r][x].fi>=l){
ans+=nxt[r][x].se;
r=nxt[r][x].fi;
}
ans+=(pref2[r]-pref2[l])-(pref1[r]-pref1[l])*(l);
int v=arr[l]-(pref1[r]-pref1[l]);
if (v<0) cout<<"-1"<<endl;
else cout<<ans/k<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4568 KB |
Output is correct |
3 |
Correct |
1 ms |
4696 KB |
Output is correct |
4 |
Correct |
2 ms |
6936 KB |
Output is correct |
5 |
Correct |
3 ms |
6744 KB |
Output is correct |
6 |
Correct |
2 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
3 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
7000 KB |
Output is correct |
13 |
Correct |
2 ms |
7004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
344 ms |
112472 KB |
Output is correct |
2 |
Correct |
372 ms |
113032 KB |
Output is correct |
3 |
Correct |
46 ms |
10112 KB |
Output is correct |
4 |
Correct |
160 ms |
109140 KB |
Output is correct |
5 |
Correct |
170 ms |
109124 KB |
Output is correct |
6 |
Correct |
317 ms |
112840 KB |
Output is correct |
7 |
Correct |
318 ms |
111380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
14160 KB |
Output is correct |
2 |
Correct |
217 ms |
116816 KB |
Output is correct |
3 |
Correct |
191 ms |
116652 KB |
Output is correct |
4 |
Correct |
192 ms |
116792 KB |
Output is correct |
5 |
Correct |
185 ms |
116816 KB |
Output is correct |
6 |
Correct |
212 ms |
110800 KB |
Output is correct |
7 |
Correct |
223 ms |
111060 KB |
Output is correct |
8 |
Correct |
231 ms |
114060 KB |
Output is correct |
9 |
Correct |
261 ms |
114132 KB |
Output is correct |
10 |
Correct |
414 ms |
118964 KB |
Output is correct |
11 |
Correct |
450 ms |
117292 KB |
Output is correct |
12 |
Correct |
331 ms |
117264 KB |
Output is correct |
13 |
Correct |
340 ms |
117080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
203 ms |
93796 KB |
Output is correct |
2 |
Correct |
240 ms |
110804 KB |
Output is correct |
3 |
Correct |
105 ms |
34132 KB |
Output is correct |
4 |
Correct |
241 ms |
113872 KB |
Output is correct |
5 |
Correct |
169 ms |
105784 KB |
Output is correct |
6 |
Correct |
172 ms |
116564 KB |
Output is correct |
7 |
Correct |
164 ms |
94648 KB |
Output is correct |
8 |
Correct |
184 ms |
116560 KB |
Output is correct |
9 |
Correct |
233 ms |
109820 KB |
Output is correct |
10 |
Correct |
218 ms |
109500 KB |
Output is correct |
11 |
Correct |
281 ms |
113876 KB |
Output is correct |
12 |
Correct |
250 ms |
113108 KB |
Output is correct |
13 |
Correct |
183 ms |
116308 KB |
Output is correct |
14 |
Correct |
165 ms |
112212 KB |
Output is correct |
15 |
Correct |
234 ms |
116308 KB |
Output is correct |
16 |
Correct |
167 ms |
112384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4568 KB |
Output is correct |
3 |
Correct |
1 ms |
4696 KB |
Output is correct |
4 |
Correct |
2 ms |
6936 KB |
Output is correct |
5 |
Correct |
3 ms |
6744 KB |
Output is correct |
6 |
Correct |
2 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
3 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
7000 KB |
Output is correct |
13 |
Correct |
2 ms |
7004 KB |
Output is correct |
14 |
Correct |
344 ms |
112472 KB |
Output is correct |
15 |
Correct |
372 ms |
113032 KB |
Output is correct |
16 |
Correct |
46 ms |
10112 KB |
Output is correct |
17 |
Correct |
160 ms |
109140 KB |
Output is correct |
18 |
Correct |
170 ms |
109124 KB |
Output is correct |
19 |
Correct |
317 ms |
112840 KB |
Output is correct |
20 |
Correct |
318 ms |
111380 KB |
Output is correct |
21 |
Correct |
62 ms |
14160 KB |
Output is correct |
22 |
Correct |
217 ms |
116816 KB |
Output is correct |
23 |
Correct |
191 ms |
116652 KB |
Output is correct |
24 |
Correct |
192 ms |
116792 KB |
Output is correct |
25 |
Correct |
185 ms |
116816 KB |
Output is correct |
26 |
Correct |
212 ms |
110800 KB |
Output is correct |
27 |
Correct |
223 ms |
111060 KB |
Output is correct |
28 |
Correct |
231 ms |
114060 KB |
Output is correct |
29 |
Correct |
261 ms |
114132 KB |
Output is correct |
30 |
Correct |
414 ms |
118964 KB |
Output is correct |
31 |
Correct |
450 ms |
117292 KB |
Output is correct |
32 |
Correct |
331 ms |
117264 KB |
Output is correct |
33 |
Correct |
340 ms |
117080 KB |
Output is correct |
34 |
Correct |
203 ms |
93796 KB |
Output is correct |
35 |
Correct |
240 ms |
110804 KB |
Output is correct |
36 |
Correct |
105 ms |
34132 KB |
Output is correct |
37 |
Correct |
241 ms |
113872 KB |
Output is correct |
38 |
Correct |
169 ms |
105784 KB |
Output is correct |
39 |
Correct |
172 ms |
116564 KB |
Output is correct |
40 |
Correct |
164 ms |
94648 KB |
Output is correct |
41 |
Correct |
184 ms |
116560 KB |
Output is correct |
42 |
Correct |
233 ms |
109820 KB |
Output is correct |
43 |
Correct |
218 ms |
109500 KB |
Output is correct |
44 |
Correct |
281 ms |
113876 KB |
Output is correct |
45 |
Correct |
250 ms |
113108 KB |
Output is correct |
46 |
Correct |
183 ms |
116308 KB |
Output is correct |
47 |
Correct |
165 ms |
112212 KB |
Output is correct |
48 |
Correct |
234 ms |
116308 KB |
Output is correct |
49 |
Correct |
167 ms |
112384 KB |
Output is correct |
50 |
Correct |
187 ms |
116808 KB |
Output is correct |
51 |
Correct |
222 ms |
110804 KB |
Output is correct |
52 |
Correct |
227 ms |
114028 KB |
Output is correct |
53 |
Correct |
430 ms |
117504 KB |
Output is correct |
54 |
Correct |
309 ms |
117188 KB |
Output is correct |
55 |
Correct |
193 ms |
116548 KB |
Output is correct |
56 |
Correct |
162 ms |
112328 KB |
Output is correct |
57 |
Correct |
148 ms |
109136 KB |
Output is correct |
58 |
Correct |
159 ms |
109084 KB |
Output is correct |
59 |
Correct |
196 ms |
114496 KB |
Output is correct |
60 |
Correct |
165 ms |
112208 KB |
Output is correct |
61 |
Correct |
431 ms |
118452 KB |
Output is correct |
62 |
Correct |
423 ms |
117172 KB |
Output is correct |
63 |
Correct |
311 ms |
116936 KB |
Output is correct |
64 |
Correct |
199 ms |
112328 KB |
Output is correct |