이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
struct BIT{
int n;
vector<int> tree;
BIT(int n = 0){
this->n = n;
this->tree.assign(n + 5, 0);
}
void update(int idx, int val){
for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
}
void update(int l, int r, int val){
update(l, val);
update(r + 1, -val);
}
int get(int idx){
if(!idx) return -2e18;
int res = 0;
for(; idx; idx-=-idx&idx) res += tree[idx];
return res;
}
};
struct Node{
int sum, lz;
Node() : sum(0), lz(0) {}
};
struct SMT{
int n;
vector<Node> tree;
SMT(int n = 0){
this->n = n;
this->tree.assign(n<<2|3, Node());
}
void down(int id, int l, int r){
if(tree[id].lz == 0) return;
int mid = (l + r)>>1;
int val = tree[id].lz;
tree[id<<1].lz += val;
tree[id<<1].sum += val*(mid - l + 1);
tree[id<<1|1].lz += val;
tree[id<<1|1].sum += val*(r - mid);
tree[id].lz = 0;
}
void update(int l, int r, int id, const int &u, const int &v, const int &val){
if(l > v || r < u) return;
if(l >= u && r <= v){
tree[id].lz += val;
tree[id].sum += val*(r - l + 1);
return;
}
down(id, l, r);
int mid = (l + r)>>1;
update(l, mid, id<<1, u, v, val);
update(mid + 1, r, id<<1|1, u, v, val);
tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
}
void update(int l, int r, int val){
update(1, n, 1, l, r, val);
}
int gsum(int l, int r, int id, const int &u, const int &v){
if(l > v || r < u) return 0;
if(l >= u && r <= v) return tree[id].sum;
down(id, l, r);
int mid = (l + r)>>1;
return gsum(l, mid, id<<1, u, v) + gsum(mid + 1, r, id<<1|1, u, v);
}
int gsum(int l, int r){
return gsum(1, n, 1, l, r);
}
};
const int MX = 300005;
int n, q, D;
int a[MX];
int ans[MX];
vector<pii> Q[MX];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> D;
for(int i=1; i<=n; i++) cin >> a[i];
cin >> q;
for(int i=1; i<=q; i++){
int l, r;
cin >> l >> r;
Q[r].push_back({l, i});
}
SMT smt(n);
BIT bit(n);
bit.update(1, 1, a[1]);
stack<int> st;
st.push(1);
for(int i=2; i<=n; i++){
bit.update(i, i, a[i]);
st.push(i);
while(1){
int dif = bit.get(st.top()) - bit.get(st.top() - 1);
if(dif >= 0) break; else dif = -dif;
int pos = st.top(); st.pop();
int pre = st.top();
int d = dif/D + !!(dif%D);
bit.update(pre, pos - 1, -d*D);
smt.update(pre, pos - 1, d);
}
for(pii qr: Q[i]){
int l, id;
tie(l, id) = qr;
if(bit.get(l) < 0) ans[id] = -1;
else ans[id] = smt.gsum(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... |