#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
ll ceil_div(ll x, ll y) {
return (x + y - 1) / y;
}
void solve() {
int n; ll k; cin >> n >> k;
vector<ll> a(n); for (auto& x : a) cin >> x;
vector<ll> diff(n-1);
for (int i = 0; i < n-1; i++) {
if (a[i] <= a[i+1])
diff[i] = max(0LL, (a[i+1] - a[i]) / k);
else
diff[i] = -ceil_div(a[i] - a[i+1], k);
}
vector<ll> ps_diff = diff;
for (int i = 1; i < n-1; i++) {
ps_diff[i] += ps_diff[i-1];
}
vector<int> prv(n-1, -2); // previous thing less than it
vector<int> stk;
for (int i = 0; i < n-1; i++) {
while (sz(stk) && ps_diff[stk.back()] >= ps_diff[i]) stk.pop_back();
if (sz(stk)) prv[i] = stk.back();
else prv[i] = ps_diff[i] > 0 ? -1 : -2;
stk.push_back(i);
}
vector<ll> suf1 = diff; suf1.push_back(0);
for (int i = sz(diff)-1; i >= 0; i--) {
suf1[i] += suf1[i+1];
}
vector<ll> suf2 = suf1;
for (int i = sz(diff)-1; i >= 0; i--) {
suf2[i] += suf2[i+1];
}
auto qry = [&](int l, int r) {
if (l > r) return 0LL;
return -(suf2[l] - suf2[r+1] - suf1[r+1] * (r - l + 1));
};
vector<ll> store(n-1);
for (int i = 0; i < n-1; i++) {
store[i] = qry(prv[i] + 2, i);
}
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r, --l, --r;
if (l == r) {
ll ans = 0;
ll p = 0;
for (int i = r-1; i >= l; i--) {
if (p >= diff[i]) {
p -= diff[i];
} else {
p = 0;
}
ans += p;
}
if (a[l] - k * p >= 0)
cout << ans << '\n';
else
cout << -1 << '\n';
continue;
}
ll ans = 0;
int c = r-1;
while (c >= 0 && prv[c] + 1 >= l) { // slow
ans += store[c];
c = prv[c];
}
ll p = 0;
if (l <= c) {
p -= (suf1[l] - suf1[c+1]);
}
ans += qry(l, c);
if (a[l] - k * p >= 0)
cout << ans << '\n';
else
cout << -1 << '\n';
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
8 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
114 ms |
21800 KB |
Output is correct |
2 |
Correct |
79 ms |
21800 KB |
Output is correct |
3 |
Correct |
41 ms |
3924 KB |
Output is correct |
4 |
Correct |
72 ms |
21192 KB |
Output is correct |
5 |
Correct |
73 ms |
21184 KB |
Output is correct |
6 |
Correct |
79 ms |
22404 KB |
Output is correct |
7 |
Correct |
71 ms |
20992 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
5204 KB |
Output is correct |
2 |
Correct |
127 ms |
24364 KB |
Output is correct |
3 |
Correct |
148 ms |
30180 KB |
Output is correct |
4 |
Correct |
128 ms |
30436 KB |
Output is correct |
5 |
Correct |
131 ms |
28888 KB |
Output is correct |
6 |
Correct |
95 ms |
24104 KB |
Output is correct |
7 |
Correct |
92 ms |
22312 KB |
Output is correct |
8 |
Correct |
101 ms |
25896 KB |
Output is correct |
9 |
Correct |
101 ms |
25680 KB |
Output is correct |
10 |
Execution timed out |
2057 ms |
21628 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
18364 KB |
Output is correct |
2 |
Correct |
73 ms |
23040 KB |
Output is correct |
3 |
Correct |
59 ms |
9552 KB |
Output is correct |
4 |
Correct |
91 ms |
26684 KB |
Output is correct |
5 |
Correct |
89 ms |
26944 KB |
Output is correct |
6 |
Correct |
95 ms |
28796 KB |
Output is correct |
7 |
Correct |
88 ms |
25376 KB |
Output is correct |
8 |
Correct |
91 ms |
30268 KB |
Output is correct |
9 |
Correct |
77 ms |
22576 KB |
Output is correct |
10 |
Correct |
70 ms |
22824 KB |
Output is correct |
11 |
Correct |
88 ms |
26128 KB |
Output is correct |
12 |
Correct |
86 ms |
26176 KB |
Output is correct |
13 |
Correct |
102 ms |
29996 KB |
Output is correct |
14 |
Correct |
85 ms |
24108 KB |
Output is correct |
15 |
Correct |
97 ms |
29736 KB |
Output is correct |
16 |
Correct |
89 ms |
25740 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 |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
8 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
114 ms |
21800 KB |
Output is correct |
15 |
Correct |
79 ms |
21800 KB |
Output is correct |
16 |
Correct |
41 ms |
3924 KB |
Output is correct |
17 |
Correct |
72 ms |
21192 KB |
Output is correct |
18 |
Correct |
73 ms |
21184 KB |
Output is correct |
19 |
Correct |
79 ms |
22404 KB |
Output is correct |
20 |
Correct |
71 ms |
20992 KB |
Output is correct |
21 |
Correct |
54 ms |
5204 KB |
Output is correct |
22 |
Correct |
127 ms |
24364 KB |
Output is correct |
23 |
Correct |
148 ms |
30180 KB |
Output is correct |
24 |
Correct |
128 ms |
30436 KB |
Output is correct |
25 |
Correct |
131 ms |
28888 KB |
Output is correct |
26 |
Correct |
95 ms |
24104 KB |
Output is correct |
27 |
Correct |
92 ms |
22312 KB |
Output is correct |
28 |
Correct |
101 ms |
25896 KB |
Output is correct |
29 |
Correct |
101 ms |
25680 KB |
Output is correct |
30 |
Execution timed out |
2057 ms |
21628 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |