Submission #854577

#	Time	Username	Problem	Language	Result	Execution time	Memory
854577		BrineTw	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	103 ms	5500 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<int> v;

    BIT(int N): N(N + 1), v(N + 2) {}
    
    inline int lb(int x) {
        return x & -x;
    }

    void update(int i, int 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';
    
    int l, r, dy;
    for (int i = 0; i < Q; i++) {
        cin >> l >> r >> dy;
        
        int 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: 0 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60