Submission #1123952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123952		njoop	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	613 ms	15064 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, q, s, t, arr[200010], l, r, x;

struct st {
    vector<int> seg;

    void init() {
        seg.assign(600010, 0);
    }

    void update(int l, int r, int idx, int val, int node) {
        if(l == r) {
            seg[node] = val;
            return;
        }
        int mid = (l+r)/2;
        if(idx <= mid) update(l, mid, idx, val, node*2);
        else update(mid+1, r, idx, val, node*2+1);
        seg[node] = seg[node*2] + seg[node*2+1];
    }

    int query(int l, int r, int ql, int qr, int node) {
        if(l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return seg[node];
        int mid = (l+r)/2;
        return query(l, mid, ql, qr, node*2) + query(mid+1, r, ql, qr, node*2+1);
    }

    void upd(int idx, int val) {
        update(1, n, idx, val, 1);
    }

    int qry(int l, int r) {
        return query(1, n, l, r, 1);
    }
};

st pos, neg;

void change(int num, int idx, int dif) {
    if(num >= 0 && num+dif < 0) {
        pos.upd(idx, 0);
        neg.upd(idx, -(num+dif));
    } else if(num < 0 && num+dif >= 0) {
        neg.upd(idx, 0);
        pos.upd(idx, num+dif);
    } else if(num+dif >= 0) {
        pos.upd(idx, num+dif);
    } else {
        neg.upd(idx, -(num+dif));
    }
}
signed main() {
    pos.init();
    neg.init();
    cin >> n >> q >> s >> t;
    n++;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }
    for(int i=2; i<=n; i++) {
        if(arr[i-1]-arr[i] >= 0) {
            pos.upd(i-1, arr[i-1]-arr[i]);
        } else {
            neg.upd(i-1, arr[i]-arr[i-1]);
        }
    }
    while(q--) {
        cin >> l >> r >> x;
        l++;
        r++;
        int dl, dr;
        if(l != 1) {
            if(pos.qry(l-1, l-1) == 0) dl = -neg.qry(l-1, l-1);
            else dl = pos.qry(l-1, l-1);
            change(dl, l-1, -x);
        }
        if(r < n) {
            if(pos.qry(r, r) == 0) dr = -neg.qry(r, r);
            else dr = pos.qry(r, r);
            change(dr, r, x);
        }
        cout << pos.qry(1, n)*t-neg.qry(1, n)*s << "\n";
    }
    return 0;
}

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