이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
struct LZ_ST {
int sz;
vector<ll> t, lz;
void init(int n) {
sz = n;
t.resize(sz * 4 + 7);
lz.resize(sz * 4 + 7);
}
inline void push(int v, int l, int r) {
if (l != r && lz[v]) {
int m = (l + r) / 2;
t[v * 2] += lz[v] * (m - l + 1);
t[v * 2 + 1] += lz[v] * (r - m);
lz[v * 2] += lz[v];
lz[v * 2 + 1] += lz[v];
}
lz[v] = 0;
}
void upd(int ql, int qr, ll x, int v, int l, int r) {
if (r < ql || l > qr)
return;
if (l >= ql && r <= qr)
t[v] += x * (r - l + 1), lz[v] += x;
else {
push(v, l, r);
int m = (l + r) / 2;
upd(ql, qr, x, v * 2, l, m);
upd(ql, qr, x, v * 2 + 1, m + 1, r);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
void upd(int ql, int qr, ll x) {
upd(ql, qr, x, 1, 1, sz);
}
ll query(int ql, int qr, int v, int l, int r) {
if (r < ql || l > qr)
return 0;
if (l >= ql && r <= qr)
return t[v];
push(v, l, r);
int m = (l + r) / 2;
return query(ql, qr, v * 2, l, m) + query(ql, qr, v * 2 + 1, m + 1, r);
}
ll query(int ql, int qr) {
return query(ql, qr, 1, 1, sz);
}
};
const int N = 3e5 + 7;
int n, q;
vector<array<int, 2>> qry[N];
ll c[N], d;
ll ans[N];
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> d;
for (int i = 1; i <= n; i++)
cin >> c[i];
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
qry[r].push_back({l, i});
}
LZ_ST st;
st.init(n + 1);
stack<array<ll, 2>> s;
s.push({(ll) 1e18, 1});
for (int i = 1; i <= n; i++) {
if (i > 1) {
if (c[i] >= c[i - 1]) {
ll dif = (c[i] - c[i - 1]) / d;
if (dif)
s.push({dif, i});
}
else {
ll dif = (c[i - 1] - c[i] + d - 1) / d;
while (dif) {
auto [x, j] = s.top();
ll take = min(x, dif);
x -= take, dif -= take;
st.upd(j, i - 1, take);
if (x == 0)
s.pop();
}
}
}
for (auto &[l, idx] : qry[i]) {
ll x = c[l] - st.query(l, l) * d;
ans[idx] = (x < 0 ? -1 : st.query(l, i));
}
}
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
return 0;
}
# | 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... |