이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
struct node {
int upd = 0;
int ans = 0;
} st[4*MAXN];
void prop(int idx) {
st[2*idx+1].upd += st[idx].upd;
st[2*idx+2].upd += st[idx].upd;
st[2*idx+1].ans += st[idx].upd;
st[2*idx+2].ans += st[idx].upd;
st[idx].upd = 0;
st[idx].ans = min(st[2*idx+1].ans, st[2*idx+2].ans);
}
void u(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
st[idx].upd += val;
st[idx].ans += val;
return;
}
int mid = (constl + constr) >> 1;
prop(idx);
if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid+1) u(l, r, constl, mid, 2*idx+1, val);
else {
u(l, r, constl, mid, 2*idx+1, val);
u(l, r, mid+1, constr, 2*idx+2, val);
}
st[idx].ans = min(st[2*idx+1].ans, st[2*idx+2].ans);
}
int qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) {
return st[idx].ans;
}
int mid = (constl + constr) >> 1;
prop(idx);
if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
else {
return qu(l, r, constl, mid, 2*idx+1);
return qu(l, r, mid+1, constr, 2*idx+2);
}
}
void update(int l, int r, int v) {
u(l, r, 0, MAXN-1, 0, v);
}
int query(int i) {
return qu(i, i, 0, MAXN-1, 0);
}
void solve(int tc) {
int n, q, S, T;
cin >> n >> q >> S >> T;
S = -S;
int cur = 0;
int a[n+1];
for(int i=0; i<=n; i++) {
cin >> a[i];
update(i, i, a[i]);
}
for(int i=1; i<=n; i++) {
if(a[i-1] < a[i]) cur += S * (a[i] - a[i-1]);
else cur += T * (a[i-1] - a[i]);
}
while(q--) {
int l, r, x;
cin >> l >> r >> x;
int f = -1;
if(query(l-1) < query(l)) cur += f * S * (query(l) - query(l-1));
else cur += f * T * (query(l-1) - query(l));
if(r < n && query(r) < query(r+1)) cur += f * S * (query(r+1) - query(r));
else if(r < n) cur += f * T * (query(r) - query(r+1));
update(l, r, x);
f = 1;
if(query(l-1) < query(l)) cur += f * S * (query(l) - query(l-1));
else cur += f * T * (query(l-1) - query(l));
if(r < n && query(r) < query(r+1)) cur += f * S * (query(r+1) - query(r));
else if(r < n) cur += f * T * (query(r) - query(r+1));
cout << cur << "\n";
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |