제출 #1095601

#제출 시각아이디문제언어결과실행 시간메모리
1095601TrinhKhanhDungFoehn Phenomena (JOI17_foehn_phenomena)C++14
30 / 100
109 ms11348 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define sz(x) (int)x.size() #define ALL(v) v.begin(),v.end() #define MASK(k) (1LL << (k)) #define BIT(x, i) (((x) >> (i)) & 1) #define oo (ll)1e18 + 10 #define INF (ll)1e9 #define MOD (ll)(1e9 + 7) using namespace std; template<class T1, class T2> bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;} template<class T1, class T2> bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;} template<class T1, class T2> void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;} template<class T1, class T2> void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;} template<class T> void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());} struct fen{ vector<ll> tree; int n; fen(int _n = 0){ n = _n; tree.resize(n + 3, 0); } void upd(int p, ll c){ for(; p <= n; p += p & -p) tree[p] += c; } ll get(int p){ ll ans = 0; for(; p > 0; p -= p & -p) ans += tree[p]; return ans; } }; const int maxN = 2e5 + 10; int N, Q, S, T; int a[maxN]; void solve(){ cin >> N >> Q >> S >> T; for(int i = 0; i <= N; i++) cin >> a[i]; ll larger = 0, smaller = 0; fen bit(N); for(int i = 1; i <= N; i++){ bit.upd(i, a[i]); bit.upd(i + 1, -a[i]); if(a[i] > a[i - 1]) larger += a[i] - a[i - 1]; else smaller += a[i - 1] - a[i]; } while(Q--){ int l, r, x; cin >> l >> r >> x; int val_l = bit.get(l); int pre_l = bit.get(l - 1); if(val_l > pre_l) larger -= val_l - pre_l; else smaller -= pre_l - val_l; int val_r = bit.get(r); int nxt_r = bit.get(r + 1); if(r < N){ if(nxt_r > val_r) larger -= nxt_r - val_r; else smaller -= val_r - nxt_r; } bit.upd(l, x); bit.upd(r + 1, -x); val_l = bit.get(l); pre_l = bit.get(l - 1); if(val_l > pre_l) larger += val_l - pre_l; else smaller += pre_l - val_l; val_r = bit.get(r); nxt_r = bit.get(r + 1); if(r < N){ if(nxt_r > val_r) larger += nxt_r - val_r; else smaller += val_r - nxt_r; } cout << -1LL * larger * S + 1LL * smaller * T << '\n'; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("bdbang.inp","r",stdin); // freopen("bdbang.out","w",stdout); int t = 1; // cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...