이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 2e6+10;
array<ll, 3> st[mxN];
ll ass[mxN];
ll s, t;
void propagate(int node, int l, int r) {
if(l == r) return;
int left = node*2, right = node*2+1;
ass[left] += ass[node];
ass[right] += ass[node];
st[left][1] += ass[node];
st[left][2] += ass[node];
st[right][1] += ass[node];
st[right][2] += ass[node];
ass[node] = 0;
}
void build(int node, int l, int r, vector<ll>& a) {
if(l == r) {
st[node] = {0, a[l], a[l]};
return ;
}
int mid = (l+r)/2;
build(node*2, l, mid, a);
build(node*2+1, mid+1, r, a);
int left = node*2, right = node*2+1;
st[node][0] = st[left][0] + st[right][0];
st[node][1] = st[left][1]; st[node][2] = st[right][2];
if(st[left][2] < st[right][1]) {
st[node][0] -= s * (st[right][1] - st[left][2]);
}
else {
st[node][0] += t * (st[left][2] - st[right][1]);
}
}
void upd(int node, int l, int r, int l1, int r1, ll x) {
propagate(node, l, r);
if(l1 <= l && r1 >= r) {
st[node][1] += x;
st[node][2] += x;
ass[node] += x;
propagate(node, l, r);
return ;
}
if(l1 > r || r1 < l) return ;
int mid = (l+r)/2;
upd(node*2, l, mid, l1, r1, x);
upd(node*2+1, mid+1, r, l1, r1, x);
int left = node*2, right = node*2+1;
st[node][0] = st[left][0] + st[right][0];
st[node][1] = st[left][1]; st[node][2] = st[right][2];
if(st[left][2] < st[right][1]) {
st[node][0] -= s * (st[right][1] - st[left][2]);
}
else {
st[node][0] += t * (st[left][2] - st[right][1]);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q >> s >> t; n++;
vector<ll> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
build(1, 0, n-1, a);
while(q--) {
int l, r; ll x;
cin >> l >> r >> x;
upd(1, 0, n-1, l, r, x);
cout << st[1][0] << '\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... |