제출 #587209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587209		PiejanVDC	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	836 ms	36892 KiB

foehn_phenomena

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

#define int long long

vector<int>st(8*200000);
vector<int>lazy(8*200000);

int l,r,x;

int query(int i, int j, int p) {
    if(i > l || j < l)
        return 0;
    if(i == j) {
        st[p] += lazy[p];
        lazy[p] = 0;
        return st[p];
    }
    lazy[2*p] += lazy[p];
    lazy[2*p+1] += lazy[p];
    lazy[p] = 0;
    int mid = (i+j)/2;
    return query(i, mid, 2*p) + query(mid+1, j, 2*p+1);
}

void update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i >= l && j <= r) {
        lazy[p] += x;
        return;
    }
    int mid = (i+j)/2;
    update(i, mid, 2*p);
    update(mid+1, j, 2*p+1);
}

signed main() {
    int n,q,s,t; cin>>n>>q>>s>>t;
    vector<int>v(n+1);
    for(auto &z : v)
        cin>>z;
    long long ans = 0;
    for(int i = 1 ; i <= n ; i++) {
        x = v[i];
        l = r = i;
        update(1, n, 1);
        if(v[i] > v[i-1])
            ans -= (v[i]-v[i-1]) * s;
        else
            ans += (v[i-1]-v[i]) * t;
    }
    while(q--) {
        cin>>l>>r>>x;
        int L = l, R = r;
        int A = query(1, n, 1);
        l = R;
        int B = query(1, n, 1);
        l = L-1;
        int a = (l == 0 ? 0 : query(1, n, 1));
        l = R+1;
        int b = (l == n+1 ? 0 : query(1, n, 1));
        l = L, r = R;
        update(1, n, 1);
        l = L;
        int nwA = query(1, n, 1);
        l = R;
        int nwB = query(1, n, 1);
        if(A >= a)
            ans += (A - a) * s;
        else
            ans -= (a - A) * t;
        if(nwA >= a)
            ans -= (nwA - a) * s;
        else
            ans += (a - nwA) * t;
        if(R < n) {
            if(b >= B)
                ans += (b - B) * s;
            else
                ans -= (B - b) * t;
            if(b >= nwB)
                ans -= (b - nwB) * s;
            else
                ans += (nwB - b) * t;
        }
        cout << ans << '\n';
    }
}

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