제출 #245273

#제출 시각아이디문제언어결과실행 시간메모리
245273WhaleVomitFoehn Phenomena (JOI17_foehn_phenomena)C++14
30 / 100
171 ms6708 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define mp make_pair #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define MOO(i, a, b) for(int i=a; i<b; i++) #define M00(i, a) for(int i=0; i<a; i++) #define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--) #define M00d(i,a) for(int i = (a)-1; i>=0; i--) #define FAST ios::sync_with_stdio(0); cin.tie(0); #define finish(x) return cout << x << '\n', 0; #define dbg(x) cerr << ">>> " << #x << " = " << x << "\n"; #define _ << " _ " << typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int,int> pi; typedef pair<ld,ld> pd; typedef complex<ld> cd; template<int sz> struct BIT { ll b[sz+1]; BIT() { M00(i, sz+1) b[i] = 0; } void add(int k, ll val) { k++; for(; k <= sz; k+=(k&-k)) b[k] += val; } int psum(int ind) { int ans = 0; ind++; for(; ind>0; ind-=(ind&-ind)) ans+=b[ind]; return ans; } ll sum(int l, int r) { return psum(r) - psum(l-1); } void upd(int l, int r, ll x) { add(l, x); if(r != sz-1) add(r+1, -x); } ll query(int idx) { return psum(idx); } }; const int MAX_N = 200200; BIT<MAX_N> st; ll S, T; ll get(int i) { ll x1 = st.query(i); ll x2 = st.query(i+1); if(x1 < x2) return -S*(x2-x1); else return T*(x1-x2); } int main() { FAST int n, q; cin >> n >> q >> S >> T; n++; vector<ll> arr(n); M00(i, n) cin >> arr[i]; M00(i, n) st.upd(i, i, arr[i]); ll ans = 0; M00(i, n-1) ans += get(i); M00(i, q) { int l, r, x; cin >> l >> r >> x; if(l != 0) ans -= get(l-1); if(r != n-1) ans -= get(r); st.upd(l,r,x); if(l != 0) ans += get(l-1); if(r != n-1) ans += get(r); cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...