이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
template <typename Arg>
void __f(string name, Arg arg) {
cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
string cur = "";
for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
string nxt = names.substr(cur.size()+2);
cerr << cur << " = " << head << ", ";
__f(nxt, tail...);
}
const int mxn = 200005;
int N, Q, S, T, ret;
int A[mxn], fw[mxn], fw2[mxn];
void update(int x, int y, int v) {
for (int tx=x; tx <= N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
for (int ty=y+1; ty <= N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y;
}
int sum(int x) {
int res = 0;
for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
return res;
}
int query(int x, int y) {
if (x == 0) return A[0];
return sum(y)-sum(x-1);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> Q >> S >> T;
for (int i = 0; i <= N; ++i) {
cin >> A[i];
if (i) update(i, i, A[i]);
}
for (int i = 0; i < N; ++i) {
int dif = abs(A[i] - A[i + 1]);
if (A[i] < A[i + 1]) ret -= dif * S;
else ret += dif * T;
}
while (Q--) {
int l, r, k;
cin >> l >> r >> k;
int lv = query(l - 1, l - 1), rv = query(r + 1, r + 1);
int dif_l = query(l, l) - lv, dif_r = rv - query(r, r);
if (dif_l > 0) ret += abs(dif_l) * S;
else ret -= abs(dif_l) * T;
if (r != N) {
if (dif_r > 0) ret += abs(dif_r) * S;
else ret -= abs(dif_r) * T;
}
update(l, r, k);
dif_l = query(l, l) - lv, dif_r = rv - query(r, r);
if (dif_l > 0) ret -= abs(dif_l) * S;
else ret += abs(dif_l) * T;
if (r != N) {
if (dif_r > 0) ret -= abs(dif_r) * S;
else ret += abs(dif_r) * T;
}
cout << ret << '\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... |