제출 #948328

#제출 시각아이디문제언어결과실행 시간메모리
948328steveonalexFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
122 ms14932 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1ULL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ll mask){return __builtin_popcountll(mask);} int ctz(ll mask){return __builtin_ctzll(mask);} int logOf(ll mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } struct FenwickTree{ ll n; vector<ll> a; FenwickTree(ll _n){ n = _n; a.resize(n+1); } void update(ll i, ll v){ while(i <= n){ a[i] += v; i += LASTBIT(i); } } ll get(ll i){ ll ans = 0; while(i > 0){ ans += a[i]; i -= LASTBIT(i); } return ans; } }; const ll N = 2e5 + 69; ll n, q; ll s, t; ll dt[N]; FenwickTree bit(N); ll ans= 0; void update(ll l, ll r, ll val){ ans -= dt[l]; ans -= dt[r+1]; bit.update(l, val); bit.update(r + 1, -val); dt[l] = bit.get(l) - bit.get(l-1); if (dt[l] > 0) dt[l] *= s; else dt[l] *= t; dt[r+1] = bit.get(r+1) - bit.get(r); if (dt[r+1] > 0) dt[r+1] *= s; else dt[r+1] *= t; ans += dt[l]; ans += dt[r+1]; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q >> s >> t; vector<ll> a(n+1); for(ll i= 0; i<=n; ++i) cin >> a[i]; for(ll i = 1; i<=n; ++i){ update(i, i, a[i]); } while(q--){ ll l, r, x; cin >> l >> r >> x; update(l, r, x); cout << -(ans - dt[n+1]) << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...