Submission #854580

#	Time	Username	Problem	Language	Result	Execution time	Memory
854580		BrineTw	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	116 ms	7344 KiB

foehn_phenomena

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
#define debug(x) cerr << #x << ' ' << x << '\n'
#define endl '\n'
 
using namespace std;
 
const int M = 1e9 + 7;
typedef long long ll;
 
struct BIT {
    int N;
    vector<ll> v;
 
    BIT(int N): N(N + 1), v(N + 2) {}
    
    inline int lb(int x) {
        return x & -x;
    }
 
    void update(int i, ll dx) {
        for (; i <= N; i += lb(i)) v[i] += dx;
    }
    
    ll query(int i) {
        ll ans = 0;
        for (; i; i -= lb(i)) ans += v[i];
        return ans;
    }
};
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int N, Q, S, T;
    cin >> N >> Q >> S >> T;
 
    vector<ll> h(N + 1);
    for (auto& n: h) cin >> n;
    
    BIT bit(N);
    ll current = 0;
    for (int i = 1; i <= N; i++) {
        if (h[i] > h[i - 1]) {
            current -= (h[i] - h[i - 1]) * S;
        } else {
            current -= (h[i] - h[i - 1]) * T;
        }
        bit.update(i, h[i] - h[i - 1]);
    }
 
//    for (auto& n: bit.v) cerr << n << " \n"[&n == &bit.v.back()];
 
    for (int i = 0; i <= N; i++) {
    //    cerr << bit.query(i) << ' ';
    }
  //  cerr << '\n';
    
    ll l, r, dy;
    for (int i = 0; i < Q; i++) {
        cin >> l >> r >> dy;
        
        ll h1, h2, h3, h4;
        h1 = bit.query(l - 1);
        h2 = bit.query(l);
        h3 = bit.query(r);
        h4 = bit.query(r + 1);
 
        if (h2 > h1) {
            current += (h2 - h1) * S;
        } else {
            current += (h2 - h1) * T;
        }
 
        if (r != N && h4 > h3) {
            current += (h4 - h3) * S;
        } else if (r != N && h4 <= h3) {
            current += (h4 - h3) * T;
        }
 
        bit.update(l, dy);
        bit.update(r + 1, -dy);
        
        h1 = bit.query(l - 1);
        h2 = bit.query(l);
        h3 = bit.query(r);
        h4 = bit.query(r + 1);
 
        current -= (h2 > h1 ? S : T) * (h2 - h1);
        if (r != N) current -= (h4 > h3 ? S : T) * (h4 - h3); 
        
        cout << current << '\n';
    }
 
    return 0;   
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60