#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);
}
auto qry = [&](int l, int r) {
ll ans = 0;
ll p = 0;
for (int i = r; i >= l; i--) {
p -= diff[i];
ans += p;
}
return ans;
};
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) {
ans += store[c];
/*
ll p = 0;
for (int i = c; i > prv[c] + 1; i--) {
p -= diff[i];
ans += p;
}
*/
c = prv[c];
}
ll p = 0;
for (int i = c; i >= l; i--) {
p -= diff[i];
// ans += p;
}
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();
}
# |
Verdict |
Execution time |
Memory |
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 |
604 KB |
Output is correct |
5 |
Correct |
5 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
4 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
4 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
484 KB |
Output is correct |
12 |
Correct |
8 ms |
344 KB |
Output is correct |
13 |
Correct |
5 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2082 ms |
10844 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
5200 KB |
Output is correct |
2 |
Execution timed out |
2077 ms |
11752 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2056 ms |
9052 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
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 |
604 KB |
Output is correct |
5 |
Correct |
5 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
4 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
4 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
484 KB |
Output is correct |
12 |
Correct |
8 ms |
344 KB |
Output is correct |
13 |
Correct |
5 ms |
348 KB |
Output is correct |
14 |
Execution timed out |
2082 ms |
10844 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |