Submission #1208774

#TimeUsernameProblemLanguageResultExecution timeMemory
1208774andrejikusFoehn Phenomena (JOI17_foehn_phenomena)C++20
30 / 100
79 ms6028 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); } #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) const int N = 2e5 + 3; ll a[N]; struct fenwick_tree { vector<int> bit; void init(int n) { bit.assign(n + 1, 0); } int sum(int i) { int s = 0; while (i > 0) { s += bit[i]; i -= (i & (-i)); } return s; } void add(int i, int val, int n) { while (i > 0 && i <= n) { bit[i] += val; i += (i & (-i)); } } int get(int l, int r) { return sum(r) - (l > 0 ? sum(l-1) : 0); } }; fenwick_tree fenwick; void solve() { ll n, q, s, t; cin >> n >> q >> s >> t; fenwick.init(n+1); for (int i = 0; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { fenwick.add(i, a[i], n+1); fenwick.add(i+1, -a[i], n+1); } ll ans = 0; for (int i = 1; i <= n; i++) { if (a[i-1] < a[i]) ans -= (a[i]-a[i-1])*s; else ans += (a[i-1]-a[i])*t; } while (q--) { ll l, r, x; cin >> l >> r >> x; int al = fenwick.get(0, l), alm1 = fenwick.get(0, l-1); int arp1 = fenwick.get(0, r+1), ar = fenwick.get(0, r); if (al > alm1) ans += (al-alm1)*s; else ans -= (alm1-al)*t; if (r < n) { if (arp1 > ar) ans += (arp1-ar)*s; else ans -= (ar-arp1)*t; } fenwick.add(r+1, -x, n+1); fenwick.add(l, x, n+1); al = fenwick.get(0, l), alm1 = fenwick.get(0, l-1); arp1 = fenwick.get(0, r+1), ar = fenwick.get(0, r); if (al > alm1) ans -= (al-alm1)*s; else ans += (alm1-al)*t; if (r < n) { if (arp1 > ar) ans -= (arp1-ar)*s; else ans += (ar-arp1)*t; } cout << ans << "\n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t=1; //cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...