제출 #945646

#제출 시각아이디문제언어결과실행 시간메모리
945646nasir_bashirovFoehn Phenomena (JOI17_foehn_phenomena)C++11
30 / 100
470 ms12112 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define db long double #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define endl '\n' #define all(x) x.begin(), x.end() #define fastio\ ios_base::sync_with_stdio(0);\ cin.tie(0);\ cout.tie(0)\ #define int long long struct fenwickTree{ int n; vi BIT; fenwickTree(int sz){ n = sz; BIT.resize(n + 1, 0); } void update(int i, int v){ if(i == 0) return; while(i <= n){ BIT[i] += v; i += i & (-i); } } int query(int l, int r){ if(l > r) return 0; if(l != 1) return query(1, r) - query(1, l - 1); int res = 0; while(r > 0){ res += BIT[r]; r -= r & (-r); } return res; } }; const int sz = 2e5 + 5; int n, q, x, y, l, r, k, res, a[sz]; signed main(){ cin >> n >> q >> x >> y; fenwickTree t(n + 1); for(int i = 1; i <= n + 1; i++){ cin >> a[i]; t.update(i, a[i] - t.query(1, i - 1)); if(i > 1){ if(a[i] <= a[i - 1]) res += y * (a[i - 1] - a[i]); else res -= x * (a[i] - a[i - 1]); } } while(q--){ cin >> l >> r >> k; l++, r++; if(l > 1 and t.query(1, l) <= t.query(1, l - 1)) res -= y * abs(t.query(1, l) - t.query(1, l - 1)); else res += x * abs(t.query(1, l) - t.query(1, l - 1)); if(r < n + 1 and t.query(1, r + 1) < t.query(1, r)) res -= y * abs(t.query(1, r + 1) - t.query(1, r)); else res += x * abs(t.query(1, r + 1) - t.query(1, r)); t.update(l, k), t.update(r + 1, -k); if(l > 1 and t.query(1, l) <= t.query(1, l - 1)) res += y * abs(t.query(1, l) - t.query(1, l - 1)); else res -= x * abs(t.query(1, l) - t.query(1, l - 1)); if(r < n + 1 and t.query(1, r + 1) <= t.query(1, r)) res += y * abs(t.query(1, r + 1) - t.query(1, r)); else res -= x * abs(t.query(1, r + 1) - t.query(1, r)); cout << res << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...