제출 #701897

#제출 시각아이디문제언어결과실행 시간메모리
701897tamthegodFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
385 ms18252 KiB
// Make the best become better // No room for laziness #include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, q, s, t; int a[maxN]; int res = 0; int st[4 * maxN], lazy[4 * maxN]; void down(int id) { int t = lazy[id]; lazy[id] = 0; st[id * 2] += t; lazy[id * 2] += t; st[id * 2 + 1] += t; lazy[id * 2 + 1] += t; } void build(int id, int l, int r) { if(l == r) { st[id] = a[l]; return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); } void update(int id, int l, int r, int u, int v, int val) { if(l > v || r < u) return; if(l >= u && r <= v) { st[id] += val; lazy[id] += val; return; } int mid = (l + r) / 2; down(id); update(id * 2, l, mid, u, v, val); update(id * 2 + 1, mid + 1, r, u, v, val); } int get(int id, int l, int r, int pos) { if(l == r) return st[id]; int mid = (l + r) / 2; down(id); if(pos <= mid) return get(id * 2, l, mid, pos); return get(id * 2 + 1, mid + 1, r, pos); } void ReadInput() { cin >> n >> q >> s >> t; for(int i=0; i<=n; i++) cin >> a[i]; for(int i=1; i<=n; i++) { if(a[i] >= a[i - 1]) res -= (a[i] - a[i - 1]) * s; else res += (a[i - 1] - a[i]) * t; } } void Solve() { build(1, 0, n); while(q--) { int l, r, x; cin >> l >> r >> x; int val1 = get(1, 0, n, l), val2 = get(1, 0, n, l - 1); if(val1 >= val2) res += s * (val1 - val2); else res -= t * (val2 - val1); if(r < n) { int val1 = get(1, 0, n, r), val2 = get(1, 0, n, r + 1); if(val2 >= val1) res += s * (val2 - val1); else res -= t * (val1 - val2); } update(1, 0, n, l, r, x); val1 = get(1, 0, n, l), val2 = get(1, 0, n, l - 1); if(val1 >= val2) res -= s * (val1 - val2); else res += t * (val2 - val1); if(r < n) { int val1 = get(1, 0, n, r), val2 = get(1, 0, n, r + 1); if(val2 >= val1) res -= s * (val2 - val1); else res += t * (val1 - val2); } cout << res << '\n'; } } int32_t main() { // freopen("sol.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...