제출 #151607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151607		blue	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	1062 ms	27872 KiB

foehn_phenomena

#include <iostream>
#include <vector>
using namespace std;

int N, Q, S, T;
int* A;

class segtree
{
    public:
    int v;
    int l;
    int r;
    
    segtree* left;
    segtree* right;
    
    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(L == R)
        {
            left = right = NULL;
            v = A[l];
        }
        else
        {
            left = new segtree(L, (L+R)/2);
            right = new segtree((L+R)/2 + 1, R);
            v = 0;
        }
    }
    
    void update(int L, int R, int U)
    {
        if(R < l || r < L) return;
        if(L <= l && r <= R) v += U;
        else
        {
            left->update(L, R, U);
            right->update(L, R, U);
        }
    }
    
    int val(int I)
    {
        if(I == 0) return 0;
        if(l == r) return v;
        return v + ((I <= (l+r)/2) ? left->val(I) : right->val(I));
    }
};

int main()
{
    cin >> N >> Q >> S >> T;
    A = new int[N+1];
    for(int i = 0; i <= N; i++) cin >> A[i];
    
    segtree B(1, N);
    
    int w = 0;
    for(int i = 1; i <= N; i++) w += (A[i-1] - A[i]) * (A[i-1] < A[i] ? S:T);
    
    int l, r, u;
    
    vector<int> res;
    for(int i = 1; i <= Q; i++)
    {
        cin >> l >> r >> u;
        w -= (B.val(l-1) - B.val(l)) * (B.val(l-1) < B.val(l) ? S:T);
        if(r != N) w -= (B.val(r) - B.val(r+1)) * (B.val(r) < B.val(r+1) ? S:T);
        B.update(l, r, u);
        w += (B.val(l-1) - B.val(l)) * (B.val(l-1) < B.val(l) ? S:T);
        if(r != N) w += (B.val(r) - B.val(r+1)) * (B.val(r) < B.val(r+1) ? S:T);
        
        res.push_back(w);
    }
    for(int r:res) cout << r << '\n';
    
    return 0;
}

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