#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q;
cin >> n >> k;
vector<int> c(n+1), ac(n+1, 0), a(n+1, 0), b(n+1, 0), aff(n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> c[i];
ac[i] = c[i];
}
int prv = n;
for (int i = n - 1; i >= 1; i--) {
if (ac[i] > ac[i + 1]) {
int diff = ac[i] - ac[i + 1];
diff = (diff + k - 1) / k;
a[i] += diff;
ac[i] -= diff * k;
} else {
int t = 0;
for (int j = i + 1; j <= prv; j++) t++, aff[j] = t;
prv = i;
}
}
int t = 0;
for (int j = 1; j <= prv; j++) t++, aff[j] = t;
for (int i = 1; i <= n; i++) a[i] += a[i - 1];
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
// cout << a[r] - a[l - 1] << '\n';
// cout << ((c[r] - ac[r]) / k) * (r - l + 1) << '\n';
int L = ac[l], R = ac[r];
L += (c[r] - R);
if (L < 0) cout << "-1\n";
else cout << a[r] - a[l - 1] - ((c[r] - ac[r]) / k) * min(aff[r], r - l + 1) << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
13764 KB |
Output is correct |
2 |
Correct |
86 ms |
17632 KB |
Output is correct |
3 |
Correct |
56 ms |
3984 KB |
Output is correct |
4 |
Correct |
102 ms |
17448 KB |
Output is correct |
5 |
Correct |
67 ms |
17488 KB |
Output is correct |
6 |
Correct |
98 ms |
17320 KB |
Output is correct |
7 |
Correct |
99 ms |
17212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
59 ms |
4944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
90 ms |
11864 KB |
Output is correct |
2 |
Correct |
108 ms |
14004 KB |
Output is correct |
3 |
Correct |
67 ms |
4688 KB |
Output is correct |
4 |
Correct |
112 ms |
13844 KB |
Output is correct |
5 |
Correct |
161 ms |
15820 KB |
Output is correct |
6 |
Correct |
114 ms |
17280 KB |
Output is correct |
7 |
Correct |
115 ms |
14744 KB |
Output is correct |
8 |
Correct |
115 ms |
17236 KB |
Output is correct |
9 |
Correct |
98 ms |
13148 KB |
Output is correct |
10 |
Correct |
68 ms |
12972 KB |
Output is correct |
11 |
Correct |
101 ms |
14024 KB |
Output is correct |
12 |
Correct |
102 ms |
13136 KB |
Output is correct |
13 |
Correct |
108 ms |
17128 KB |
Output is correct |
14 |
Correct |
83 ms |
13072 KB |
Output is correct |
15 |
Correct |
125 ms |
16980 KB |
Output is correct |
16 |
Correct |
83 ms |
12952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |