이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}
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 (prv[c] + 1 >= l) {
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;
}
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |