제출 #999076

#제출 시각아이디문제언어결과실행 시간메모리
999076coolboy19521Foehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
267 ms28768 KiB
#pragma GCC optimize("Ofast") #include"bits/stdc++.h" #define int long long using namespace std; const int sz = 2e5 + 10; int st[sz * 8], lz[sz * 8], a[sz], b[sz]; void build(int le, int ri, int v) { if (le == ri) { st[v] = a[le]; return; } int mi = le + (ri - le) / 2; build(le, mi, v * 2); build(mi + 1, ri, v * 2 + 1); } void relax(int v) { st[v] += lz[v]; lz[v * 2] += lz[v]; lz[v * 2 + 1] += lz[v]; lz[v] = 0; } void update(int le, int ri, int ql, int qr, int v, int k) { if (le > qr || ri < ql) return; if (ql <= le && ri <= qr) { lz[v] += k; relax(v); return; } int mi = le + (ri - le) / 2; update(le, mi, ql, qr, v * 2, k); update(mi + 1, ri, ql, qr, v * 2 + 1, k); } int query(int le, int ri, int ql, int qr, int v) { relax(v); if (le > qr || ri < ql) return 0; if (ql <= le && ri <= qr) { a[le] = st[v]; return st[v]; } int mi = le + (ri - le) / 2; int lq = query(le, mi, ql, qr, v * 2); int rq = query(mi + 1, ri, ql, qr, v * 2 + 1); return lq + rq; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); int n, q, s, t; cin >> n >> q >> s >> t; int tm; cin >> tm; int r = 0; for (int i = 1; i <= n; i ++) { cin >> a[i]; int d = a[i - 1] - a[i]; if (0 < d) { b[i] = d * t; } else { b[i] = d * s; } r += b[i]; } build(1, n, 1); while (q --) { int le, ri, x; cin >> le >> ri >> x; update(1, n, le, ri, 1, x); query(1, n, le, le, 1); query(1, n, ri, ri, 1); query(1, n, le - 1, le - 1, 1); if (ri + 1 <= n) { query(1, n, ri + 1, ri + 1, 1); } // cout << a[le] << ' ' << a[ri] << '\n'; r -= b[le]; int d = a[le - 1] - a[le]; if (0 < d) { b[le] = d * t; } else { b[le] = d * s; } if (ri + 1 <= n) { d = a[ri] - a[ri + 1]; r -= b[ri + 1]; if (0 < d) { b[ri + 1] = d * t; } else { b[ri + 1] = d * s; } r += b[ri + 1]; } r += b[le]; cout << r << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...