제출 #224408

#제출 시각아이디문제언어결과실행 시간메모리
224408DS007Foehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
653 ms24188 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; class seg_tree { int *t, *lazy; int n; public: seg_tree() { t = new int[1]; lazy = new int[1]; } void build(int v, int l, int r, int a[]) { if (l == r) { t[v] = a[l]; return; } int mid = (l + r) / 2; build(v * 2, l, mid, a); build(v * 2 + 1, mid + 1, r, a); t[v] = t[v * 2] + t[v * 2 + 1]; } void build(int n_, int a[]) { n = n_; t = new int[n * 8 + 8]; lazy = new int[n * 8 + 8]; build(1, 0, n, a); fill(lazy, lazy + 4 * n, 0); } void push_down(int v, int l, int r) { t[v] += lazy[v] * (r - l + 1); lazy[v * 2] += lazy[v]; lazy[v * 2 + 1] += lazy[v]; lazy[v] = 0; } int query(int v, int l, int r, int tl) { push_down(v, l, r); if (l == r && l == tl) return t[v]; int mid = (l + r) / 2; if (tl <= mid) return query(v * 2, l, mid, tl); else return query(v * 2 + 1, mid + 1, r, tl); } void update(int v, int l, int r, int tl, int tr, int x) { push_down(v, l, r); if (tl > tr) { return; } else if (l == tl && r == tr) { lazy[v] += x; push_down(v, l, r); return; } int mid = (l + r) / 2; update(v * 2, l, mid, tl, min(tr, mid), x); update(v * 2 + 1, mid + 1, r, max(mid + 1, tl), tr, x); } }; int n, q, s, t, cur; int a[N]; seg_tree st; void adjust(int x, int y, int off) { if (x < y) cur -= off * s * (y - x); else cur += off * t * (x - y); } void solveTestCase() { cin >> n >> q >> s >> t; for (int i = 0; i <= n; i++) cin >> a[i]; st.build(n, a); for (int i = 1; i <= n; i++) adjust(a[i - 1], a[i], 1); for (int i = 0; i < q; i++) { int l, r, x; cin >> l >> r >> x; int left = st.query(1, 0, n, l - 1), pl = st.query(1, 0, n, l), cl = pl + x; adjust(left, pl, -1); adjust(left, cl, 1); if (r != n) { int right = st.query(1, 0, n, r + 1), pr = st.query(1, 0, n, r), cr = pr + x; adjust(pr, right, -1); adjust(cr, right, 1); } st.update(1, 0, n, l, r, x); cout << cur << "\n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int test = 1; // cin >> test; for (int i = 1; i <= test; i++) solveTestCase(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...