Submission #951115

#TimeUsernameProblemLanguageResultExecution timeMemory
951115dwuyFoehn Phenomena (JOI17_foehn_phenomena)C++14
0 / 100
120 ms4948 KiB
#include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) int32_t(s.length()) #define MASK(k)(1LL<<(k)) #define TASK "test" #define int long long using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 200005; struct BIT{ int n; vector<int> tree; BIT(int n=0){ this->n = n; this->tree.assign(n+5, 0); } void update(int idx, int val){ for(; idx<=n; idx+=-idx&idx) tree[idx] += val; } int get(int idx){ int res = 0; for(; idx; idx-=-idx&idx) res += tree[idx]; return res; } }; int n, q, S, T; int a[MX]; void nhap(){ cin >> n >> q >> S >> T; for(int i=0; i<=n; i++) cin >> a[i]; } void solve(){ int ans = 0; BIT bit(n + 5); for(int i=1; i<=n; i++){ bit.update(i, a[i]); bit.update(i+1, -a[i]); ans += a[i] > a[i-1]? -S*(a[i] - a[i-1]) : T*(a[i-1] - a[i]); } cout << ans << endl; while(q--){ int l, r, val; cin >> l >> r >> val; if(r != n) ans -= bit.get(r+1) > bit.get(r) ? -S*(bit.get(r+1) - bit.get(r)) : T*(bit.get(r) - bit.get(r+1)); ans -= bit.get(l) > bit.get(l-1)? -S*(bit.get(l) - bit.get(l-1)) : T*(bit.get(l-1) - bit.get(l)); bit.update(l, val); bit.update(r+1, -val); if(r != n) ans += bit.get(r+1) > bit.get(r) ? -S*(bit.get(r+1) - bit.get(r)) : T*(bit.get(r) - bit.get(r+1)); ans += bit.get(l) > bit.get(l-1)? -S*(bit.get(l) - bit.get(l-1)) : T*(bit.get(l-1) - bit.get(l)); cout << ans << endl; } } int32_t main(){ fastIO; //file(TASK); nhap(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...