/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 3e5+100, M = 1e5+10, K = 20, MX = 30;
int n, q, to[N][K];
ll D, C[N], B[N], suf[N], arr[N], rmq[N][K], pref[N], S[N], dp[N][K];
array<ll, 2> L[N];
ll get(int l, int r){
int k= log2(r-l+1);
return min(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
void solve(){
cin >> n >> D;
for(int i = 1; i <= n; ++i) cin >> C[i];
B[1] = C[1] % D;
for(int i = 2; i <= n; ++i){
if(C[i] % D >= C[i-1] % D){
B[i] = B[i-1] + (C[i]%D)-(C[i-1]%D);
}else{
B[i] = B[i-1] + D + (C[i]%D)-(C[i-1]%D);
}
}
for(int i = 1; i <= n; ++i) arr[i] = rmq[i][0] = C[i] - B[i];
for(int j = 1; j < K ;++j){
for(int i = 1; i + (1<<j) <= n+1; ++i){
rmq[i][j] = min(rmq[i][j - 1], rmq[i+(1<<(j-1))][j-1]);
}
}
pref[0] = 0;
S[0] = 0;
C[0] = arr[0] = 0;
for(int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + B[i];
for(int i = 1; i <= n; ++i) S[i] = S[i - 1] + C[i];
deque<pair<ll, int>> Q;
L[1] = {0, arr[1]};
to[1][0] = L[1][0];
dp[1][0] = arr[1] * (1 - to[1][0]);
Q.pb({arr[1], 1});
for(int i = 2; i <= n; ++i){
while(!Q.empty() && Q.back().first > arr[i]) Q.pop_back();
if(Q.empty()) L[i] = {0, arr[i]};
else L[i] = {Q.back().second, arr[i]};
to[i][0] = L[i][0];
dp[i][0] = arr[i] * (i - to[i][0]);
Q.pb({arr[i], i});
}
for(int j = 1; j < K; ++j) for(int i = 1; i <= n; ++i){
dp[i][j] = dp[i][j - 1] + dp[to[i][j - 1]][j - 1];
to[i][j] = to[to[i][j - 1]][j - 1];
}
// for(int i = 1; i <= n; ++i) cout << B[i] << ' ';en;
// for(int i = 1; i <= n; ++i) cout << arr[i] << ' ';en;
// for(int i = 1; i <= n; ++i) cout << L[i][0] << ' ';en;
cin >> q;
for(int i = 1; i <= q; ++i){
int l, r; cin >> l >> r;
ll ans = 0;
ll mn = get(l, r);
ll R = B[l] - (C[l]%D);
if(mn + R < 0){
cout << -1 << '\n';
continue;
}
// cout << R << ' ';
ans = ( S[r] - S[l-1] - (pref[r] - pref[l-1] - (r-l+1)*R));
ans -= R*(r-l+1);
// cout << S[r] - S[l-1] << ' ' << pref[r]-pref[l-1] << '\n';
int p = r;
for(int j = K-1; j >= 0; --j){
if(to[p][j] >= l){
ans -= dp[p][j];
p = to[p][j];
}
}
ans -= (p-l+1)*arr[p];
// while(p > l-1){
// if(L[p][0] < l){
// ans -= (arr[p] + R) * (p - l + 1);
// }else{
// ans -= (arr[p] + R) * (p - L[p][0]);
// }
// p = L[p][0];
// }
if(ans % D != 0) cout << -1 << '\n';
else
cout << ans / D << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:104:15: warning: unused variable 'aa' [-Wunused-variable]
104 | int tt = 1, aa;
| ^~
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
1884 KB |
Output is correct |
5 |
Correct |
2 ms |
1884 KB |
Output is correct |
6 |
Correct |
2 ms |
1372 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
2 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
2 ms |
1884 KB |
Output is correct |
11 |
Correct |
2 ms |
1936 KB |
Output is correct |
12 |
Correct |
2 ms |
1884 KB |
Output is correct |
13 |
Correct |
2 ms |
1840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
444 ms |
142928 KB |
Output is correct |
2 |
Correct |
409 ms |
143556 KB |
Output is correct |
3 |
Correct |
68 ms |
4664 KB |
Output is correct |
4 |
Correct |
225 ms |
139600 KB |
Output is correct |
5 |
Correct |
247 ms |
139688 KB |
Output is correct |
6 |
Correct |
372 ms |
141928 KB |
Output is correct |
7 |
Correct |
357 ms |
141916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
8600 KB |
Output is correct |
2 |
Correct |
287 ms |
147280 KB |
Output is correct |
3 |
Correct |
268 ms |
147256 KB |
Output is correct |
4 |
Correct |
256 ms |
147284 KB |
Output is correct |
5 |
Correct |
258 ms |
147328 KB |
Output is correct |
6 |
Correct |
283 ms |
141140 KB |
Output is correct |
7 |
Correct |
300 ms |
141208 KB |
Output is correct |
8 |
Correct |
308 ms |
144468 KB |
Output is correct |
9 |
Correct |
311 ms |
144496 KB |
Output is correct |
10 |
Correct |
459 ms |
147376 KB |
Output is correct |
11 |
Correct |
456 ms |
147540 KB |
Output is correct |
12 |
Correct |
458 ms |
147536 KB |
Output is correct |
13 |
Correct |
387 ms |
147508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
282 ms |
117908 KB |
Output is correct |
2 |
Correct |
329 ms |
141136 KB |
Output is correct |
3 |
Correct |
117 ms |
35668 KB |
Output is correct |
4 |
Correct |
300 ms |
144224 KB |
Output is correct |
5 |
Correct |
264 ms |
130292 KB |
Output is correct |
6 |
Correct |
245 ms |
147016 KB |
Output is correct |
7 |
Correct |
212 ms |
117584 KB |
Output is correct |
8 |
Correct |
246 ms |
147028 KB |
Output is correct |
9 |
Correct |
263 ms |
140368 KB |
Output is correct |
10 |
Correct |
242 ms |
139984 KB |
Output is correct |
11 |
Correct |
324 ms |
144320 KB |
Output is correct |
12 |
Correct |
280 ms |
143508 KB |
Output is correct |
13 |
Correct |
239 ms |
147004 KB |
Output is correct |
14 |
Correct |
237 ms |
142928 KB |
Output is correct |
15 |
Correct |
250 ms |
146888 KB |
Output is correct |
16 |
Correct |
226 ms |
142916 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 |
2 ms |
1884 KB |
Output is correct |
5 |
Correct |
2 ms |
1884 KB |
Output is correct |
6 |
Correct |
2 ms |
1372 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
2 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
2 ms |
1884 KB |
Output is correct |
11 |
Correct |
2 ms |
1936 KB |
Output is correct |
12 |
Correct |
2 ms |
1884 KB |
Output is correct |
13 |
Correct |
2 ms |
1840 KB |
Output is correct |
14 |
Correct |
444 ms |
142928 KB |
Output is correct |
15 |
Correct |
409 ms |
143556 KB |
Output is correct |
16 |
Correct |
68 ms |
4664 KB |
Output is correct |
17 |
Correct |
225 ms |
139600 KB |
Output is correct |
18 |
Correct |
247 ms |
139688 KB |
Output is correct |
19 |
Correct |
372 ms |
141928 KB |
Output is correct |
20 |
Correct |
357 ms |
141916 KB |
Output is correct |
21 |
Correct |
67 ms |
8600 KB |
Output is correct |
22 |
Correct |
287 ms |
147280 KB |
Output is correct |
23 |
Correct |
268 ms |
147256 KB |
Output is correct |
24 |
Correct |
256 ms |
147284 KB |
Output is correct |
25 |
Correct |
258 ms |
147328 KB |
Output is correct |
26 |
Correct |
283 ms |
141140 KB |
Output is correct |
27 |
Correct |
300 ms |
141208 KB |
Output is correct |
28 |
Correct |
308 ms |
144468 KB |
Output is correct |
29 |
Correct |
311 ms |
144496 KB |
Output is correct |
30 |
Correct |
459 ms |
147376 KB |
Output is correct |
31 |
Correct |
456 ms |
147540 KB |
Output is correct |
32 |
Correct |
458 ms |
147536 KB |
Output is correct |
33 |
Correct |
387 ms |
147508 KB |
Output is correct |
34 |
Correct |
282 ms |
117908 KB |
Output is correct |
35 |
Correct |
329 ms |
141136 KB |
Output is correct |
36 |
Correct |
117 ms |
35668 KB |
Output is correct |
37 |
Correct |
300 ms |
144224 KB |
Output is correct |
38 |
Correct |
264 ms |
130292 KB |
Output is correct |
39 |
Correct |
245 ms |
147016 KB |
Output is correct |
40 |
Correct |
212 ms |
117584 KB |
Output is correct |
41 |
Correct |
246 ms |
147028 KB |
Output is correct |
42 |
Correct |
263 ms |
140368 KB |
Output is correct |
43 |
Correct |
242 ms |
139984 KB |
Output is correct |
44 |
Correct |
324 ms |
144320 KB |
Output is correct |
45 |
Correct |
280 ms |
143508 KB |
Output is correct |
46 |
Correct |
239 ms |
147004 KB |
Output is correct |
47 |
Correct |
237 ms |
142928 KB |
Output is correct |
48 |
Correct |
250 ms |
146888 KB |
Output is correct |
49 |
Correct |
226 ms |
142916 KB |
Output is correct |
50 |
Correct |
245 ms |
147280 KB |
Output is correct |
51 |
Correct |
281 ms |
141136 KB |
Output is correct |
52 |
Correct |
320 ms |
144468 KB |
Output is correct |
53 |
Correct |
450 ms |
147540 KB |
Output is correct |
54 |
Correct |
393 ms |
147540 KB |
Output is correct |
55 |
Correct |
251 ms |
147024 KB |
Output is correct |
56 |
Correct |
218 ms |
142912 KB |
Output is correct |
57 |
Correct |
198 ms |
139604 KB |
Output is correct |
58 |
Correct |
197 ms |
139600 KB |
Output is correct |
59 |
Correct |
249 ms |
144976 KB |
Output is correct |
60 |
Correct |
212 ms |
142756 KB |
Output is correct |
61 |
Correct |
461 ms |
147380 KB |
Output is correct |
62 |
Correct |
469 ms |
147504 KB |
Output is correct |
63 |
Correct |
415 ms |
147312 KB |
Output is correct |
64 |
Correct |
223 ms |
142672 KB |
Output is correct |