Submission #1109551

#TimeUsernameProblemLanguageResultExecution timeMemory
1109551Zero_OPFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
129 ms13896 KiB
#include <bits/stdc++.h> using namespace std; struct Fenwick{ vector<long long> bit; Fenwick(int n) : bit(n + 1, 0) {} void update(int id, long long val){ for(; id < (int)bit.size(); id += id & (-id)){ bit[id] += val; } } void updateRange(int l, int r, long long delta){ update(l, delta); update(r + 1, -delta); } long long query(int id){ long long sum = 0; for(; id > 0; id -= id & (-id)){ sum += bit[id]; } return sum; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int N, Q, S, T; cin >> N >> Q >> S >> T; vector<int> a(N + 1); for(int i = 0; i <= N; ++i){ cin >> a[i]; } long long cur = 0; vector<long long> diff(N + 1); for(int i = 1; i <= N; ++i){ diff[i] = abs(a[i] - a[i - 1]); cur += (a[i - 1] < a[i] ? -S : +T) * diff[i]; } Fenwick ft(N + 1); auto cost = [&](int i){ long long pre = a[i - 1] + ft.query(i - 1), cur = a[i] + ft.query(i); long long delta = abs(cur - pre); if(pre < cur) delta *= -S; else delta *= T; return delta; }; while(Q--){ int l, r; long long x; cin >> l >> r >> x; cur -= cost(l); if(r < N) cur -= cost(r + 1); ft.updateRange(l, r, x); cur += cost(l); if(r < N) cur += cost(r + 1); cout << cur << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...